Look what I found
http://zamzar.com/
free, automatic file conversion on the web, dozens of formats. Only drawback is limit of 100 MB - still, that's plenty for a youtube video. It's pretty impressive for files of the right size. There's also a special youtube URL converter, really convenient.
It's important to read the FAQ - you find out that they hold converted files for only 24 hours so you can't wait too long to retrieve.