I agree with booboo773 on not trying to upgrade the firmware on your player. All you need to do is browse the "Dead Players" section of the forum to see what I mean. The time and hassels to recover a dead player from flashing an incompatible firmware is not worth it as looking at the posts in the "Dead Players" section of the firmware, you'll see what I mean.
I haven't tried converting .mp4 files to .AMV directly before so if you're having problems, I would say that the MP3 Player Utilities probably isn't able to convert them to .AMV properly. You might have more success converting the .MP4 files to .AVI firstly then converting them to .AMV. Annoying I know, but unfortunately the MP3 Player Utilities isn't all that advanced.
What version of the MP3 Player Utilities are you using? Try a different or later version if you can to see if that helps.
Also, try using this tool instead to see if that is better at converting to .AMV video files for you --> Bytessence MPxConverter (Windows)
Let me know how you get on.