Maybe their quality settings stink. Most likely they transcode with a low setting to keep size small.

Maybe you should try converting yourself before uploading so they don't transcode. Try this or similar. Google "To FLV converter".

If all fails, Vimeo, as other sites, support HD video. You could try upscaling the video first, on PC, at a minimal loss of quality, then uploading in 720p.