I have tried loads of video conversion softwares for Ubuntu and frankly speaking have been disappointed by most of them. The few which exists are in no way "bug free". However the other day I stumbled upon devede. It has a really cool user friendly interface and the video conversion process is super sleek and quite fast. And it can virtually convert anything to anything! It reminds me of ConvertX for Windows.
At last Ubuntu has found a real contender for the post of video conversion software.