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