I've been using FlashGot for a while, which is by the same people who make DownThemAll (a great download manager), so they two addons play nicely with each other. I just tried it on a HD Test video on YouTube, and it offered me two files: a smaller FLV (Flash Video) file, and a larger MP4 video, which was huge: about 25MB for 90 seconds of video. On this Windows machine I'm on right now, I don't have the right codecs installed to play either, but I'll transfer them to Linux and see how they look.
edit: the MP4 file is HD alright: 1280 x 720, H.264 / AVC, 30fps. My poor little netbook can't play that back at 30fps, but it looks very nice. Note that when it comes to playback, once you have the right Codec installed, the "media player" in question hardly matters. It could be Media Player Classic, Windows Media Player, VLC, or almost any "front end". They often go together, but on Windows I like Media Player Classic, which is a no frills player. I just need the H.264 codec to play it back there, perhaps
x264.