I'm using Xilsoft Video Converter Ultimate and it works perfectly for me. I chose the BlackBerry MP4 preset and tweaked it, now I get full screen and it looks great on the BB.
I set the Video Size to 480x360, bitrate to 512 and frame rate to 29.97 for NTSC. I left the size and ratio alone, and set the audio bitrate to 112K. After that, save the profile and you're set to convert!
I know they also have ad-supported versions where you have to click through 100 pages, but they give it to you for free. Have to dig around for that, but here's the info page.
Mobile Video Converter: MP4 mobile converter, 3GP mobile converter