zifis
The only time I got the "video format not supported" error was when playing an mp4 video with very high video bitrate (over 1500).

Impossible as it may seem check out the pre-update recorded vids properties and compare them to the ones you can playback.

Another idea would be to move the vids to another folder or rename them.