I recently purchases a Song Walkman which has great video capabilities – provided you know how to encode the video.

It’s not very hard, simply chuck the video into handbrake and let it churn out a Sony Walkman compatible video:
handbrake -i $input_name -o $output_name.mp4 -f mp4 -e ffmpeg -E faac -w 320 -l 240 -b 500

If you don’t have this program, use the following options in any video converter program:
width: 320px
height: 240px
audio encoder: faac
video encoder: ffmpeg
output format: mp4
video bitrate: 500 kb/s