Have you guys done a tune up in your cars yet?? like plugs, wires, cap & rotor, air filter, fuel filter, all this stuff would have a lot to do if your car keeps doing this.
Also have you ever considered that maybe its just weather related?? My car does this sometimes too.. mind you my car is an 89 with almost 340,000km's on it...

but it still starts like a pro on -30C temps.
I could also see your original concern about the oil, maybe your car is very low on oil and this is him telling you.. I need some oil man! I'm metal to metal over here!