For personal use, I use mencoder (comes with mplayer) to convert just about anything into reasonable formats. It's fully command line driven so it should be easy to use from perl.

Most linux standard distros ship versions of mplayer with many codecs disabled because of copyright & patent issues. If you want the full range, get all the codecs and the source off the mplayer site and compile it yourself.

Another option might be VLC, which has python (but apparently not perl) bindings .

Yet another option: gstreamer has perl bindings and some video support. It might be overkill and I'm not sure how many codecs it supports, but it's certainly the most flexible of the three in terms of video/audio processing.