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,MBSTRING 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


Update:

Chrome Console spits this out:

prototype.js:1530 POST /checkout/onepage/saveBilling/ 500 (Internal Server Error)

Ajax.Request.Class.create.request @ prototype.js:1530
Ajax.Request.Class.create.initialize @ prototype.js:1495
(anonymous function) @ prototype.js:429
klass @ prototype.js:101Billing.save @ /skin/frontend/base/default/js/opcheckout.js:313
onclick @ /checkout/onepage/:679

UPDATE:
Apache Logs have these types of errors:

24.87.30.186 - - [21/Apr/2016:16:13:43 -0700] "POST /checkout/onepage/saveBilling/ HTTP/1.1" 500 - "https://www.example.com/checkout/onepage/" "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/49.0.2623.112 Safari/537.36"


216.129.65.170 - - [21/Apr/2016:16:08:00 -0700] "GET /checkout/onepage/progress/?toStep=payment HTTP/1.1" 500 461 "https://www.example.com/checkout/onepage/" "Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/49.0.2623.112 Safari/537.36"

216.129.65.170 - - [21/Apr/2016:16:08:00 -0700] "GET /checkout/onepage/progress/?toStep=payment HTTP/1.1" 500 461 "https://www.example.com/checkout/onepage/" "Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/49.0.2623.112 Safari/537.36"