I'm having sililar issues with my wrx. I'll start it, I hear it turn over, then it will not start up. Then i got to try a couple more times and then it will start. But this only happens sometimes. I'll try a fuel filter. I thought the dealership would have taken care of if before selling the car but it came with a dirty air filter and worn blades so I'll replace the fuel filter.
Ok I realized I maybe didn't read the whole thread, this is a whole diffrent issue entirely. Good luck. I chagned my fuel filter and now it seems to start fine.