I had similar problem with similar files before and I think I didn't encode it compabile with hd players. I digged internet and found a interactice shell script for doing all the hard parts for me. It's xvidenc
I runs it like this;
xvidenc -2p hwsdpal
-2p tells it to do two pass encode and hwsdpal tells it to use Stand-alone HW compatible SD preset (It has several presets for easy configuration. You can seem them with xvidenc -help). After you run the script, just follow the instructions on the terminal and it will do the encoding. You can see the MEcoder command before it runs MEncoder as well. Maybe YOu can use it as a reference.