I get the same thing. To me it is also related to 'pausing' as well, if I pause a video file (All formats) it hangs, then tells me it doesn't support the file format (Though it did prior to pausing) Once one file has crashed they all become 'unsupported'. Rebooting resolves everything until I 'pause' or play a 'home taken' video.

I am yet to find a decent replacement player though.

In the meantime I just don't play video files anymore and add it to the list of reasons to hate the phone.