You can also use this:
http://www.youtube-mp3.org/
Haven't tried vidtomp3 yet (but will!) but they appear to work the same way. The conversion is done on the host server so it's very quick. Odd really - the youtube-mp3 intro finishes with mention of needing 3-4 minutes to convert. In my experience it's never taken more than about 5 seconds, usually even less!
I used to use YouTube Downloader. It was slow but OK - but I started to have big problems with it refusing to convert protected content; a bit daft when you consider how much of it was infringing copyright by being on YouTube in the first place. I think it was someone on here who recommended the web-based one I now use.