Ah, never mind the official Java YouTube streamer, emTube is still streets ahead, and pulling further away all the time. The author has quietly sneaked a big update, v1.0.10, online in the last couple of days. This includes lots of tweaks and fixes, plus a new 'Sort by' option and a way of scanning your disks for flash video files. See below for the link and the changelog.

emTube is here, at http://www.emtube.yoyo.pl/  

Changelog:
Fixed the infamous 404 error.
New: emTube searches now include restricted content.
New: added Spanish, Bulgarian and Hebrew translations.
New: added "sort by" option to the search view, also available as an settings option.
Fixed problems with playback of FLV files generated by SUPER conversion program.
Fixed: download percentage on the navigation pane wasn't updated in some circumstances.
New: Saved clips view now includes an option to scan your phone memory / memory card for flash video files.
Fixed: A lot of bug fixes and small changes suggested by users to improve usability.