I'm having crazy issues on checkout page - it kicks the client out of the checkout:
 
500 Server error on /checkout/onepage/progress/?toStep=shipping_method
 
sometimes on billing too.
 
The issue is intermittent, sometimes it shows up, sometimes not.
 
SUPEE 7405
I have applied both 1.0 and 1.1 via FTP(direct file upload), but the issue with checkout still persists!
 
Please help!

PS: Both MCRYPT and SOAP are enabled on the server. I'm running PHP 5.4.45 with APC 3.1.13 on 1230 Intel CPU, 16GB of RAM, 2TB Drives