I can't believe I missed this. VLC allows you to easily convert videos. Simply go to Media > Convert / Save, select the video(s) you want to convert, then press the "Convert / Save" button and you'll be able to choose from different codecs, etc:
Thanks to Ubuntu Life & JSBlog for the info!