I have a number of mp4 (actually, m4v) files that my daughter wanted to have on her Sansa Fuze. Unfortunately, the application for Ubuntu (video4fuze) would not accept some of the files. I got around this by running a command like:
ffmpeg -i "input video.mp4" -r 25 ~/output_video.avi
This would convert the mp4 file to avi, as well as force a frame rate. Without the "-r" parameter, sometimes there would be fast sound and slow video (unsynchronized). After doing this, run video4fuze with the other file, and you will have a new file to upload to your Fuze.