After much searching/trying stuff I have found a way to successfully re-encode videos that can play on my Blackberry Pearl.
mencoder -vf expand=:::::4/3,scale=240:180 "[entervideohere]" -o "[enteroutputhere]" -of avi -ovc lavc -oac mp3lame -lavcopts vcodec=mpeg4:vbitrate=230:acodec=mp3:abitrate=64
Obviously you need to have mencoder installed
I am not completely sure what other dependencies there are, since I tried installing so many different tools….but I THINK you need the following: lame, ffmpeg .
