My car occassionally seems to be a bit pissy about turning over. Unfortunately it happens both with remote start and with a traditional key based start so there's no way to peg it on one process over the other. It always eventually turns over, but sometimes it takes awhile to get there and I start to panic, remembering how my last car started with similiar symptoms and went downhill from there.
I'm in central TX, so it's not a cold weather issue for me, and it seems to happen only sporadically. When I took it to the dealership, one of their happy helpers wrote it up as "low power during start" and of course, they were unable to recreate it. At the same time however, they fixed an electrical problem in my car (only obvious as maplights were not working) and since picking it back up (within the last month), I've not yet had another starting issue.
So sorry to hear your car has been such a nightmare!