Found the following link to RIM's support page from a review of the 8830 on MobileTechReview. BlackBerry Search Results
It details the supported audio and video formats for the 880/8830. Not surprisingly, you're having lots of problems because the media player on the 8830 is extremely picky about what it plays. I've been playing with MythTV transcoding using mencoder and ffmpeg and have had mixed success. When I get a formula that works, I'll post to this thread.