It only happen with some formats
Problem may be with your mencoder installation, that is not converting the video to FLV format properly.

Delete the file templates_c/debug.txt

and upload a new video. Now check the file, you will get information on convert command, try running the command on the server (you can do it with PHP script or ask your server admin to do it for you) to see if video get converted to FLV format.