Ok, I've had my phone for a week now and I've run into this same problem. I don't have any videos saved to either the phone or the card, but I do take little test videos and until this day they would playback.
I've tried resetting to the default camera settings, but nothing changes. Anyone have a clear explination of what's wrong?
***UPDATE***
Ok, well I fixed the problem, the only thing was that I had to format the SD card. I guess if this happens again I'll have to remember to back up the videos to my computer or online before fixing it.