Late update for people who ends up in this thread looking for a solution to the same problem.
It was the CPS (crankshaft position sensor)
I bought this one on Amazon for $90 and it works wonders. Car never has problem turning on again.
http://www.amazon.com/gp/product/B006K8ZHOU