I've been using the script above for quite a while with minor tweaks here and there for aspect ratio and stuff like that. But recently some update broke the thing and the fix was to add the following to the mencoder command line:
I'm not sure what it does exactly but it worked. Actually, -srate 8000 was what I had originally, but when I played it back on the BB, there was no sound. So I doubled it and the sound worked.
Device: Blackberry 8100 v126.96.36.199
Carrier: T-Mobile USA
Desktop OS: Fedora 7 Linux, Windows XP (vmware)