VLC is crap for converting, it never gets the right codecs. I know, i could manually ajust them, but there are other programs that can fetch them automatically, so I kinda expect that from a program in 2010.
I found a Program, that converts and comes with all the required plug-ins and Codecs.
WinFF it's called. Don't ask me why it's called so, it aint got nothing to do with windows.
Can be installed via Synaptic.