I was also wondering how to convert some videos so that the phone could play them. As I use GNU/Linux, I could not get it working properly for a long time. I used ffmpeg with h263 codec, but the audio was mute. Then I found that I need to compile the amr* codecs and now I have sound as well. If someone is interested, I can post the details.