Avoid anything that says "U3" on it.
Why? I've got a SanDisk U3 2 GB drive that I use a lot. It was cheap and works well.
It does mount 2 disk devices when you plug it in which is a bit annoying (a read only filesystem with some utilties, and the main thumbdrive), but I've actually had use for those utilities.
Reliability issues, or just didn't like the software?
I hear the 16GB flash drives are getting cheaper by the hour...
Good to hear. I just got myself an Asus Eee. With a 16 gig flash, I'll be able to boot an entirely separate Linux distro and files from the SD slot. Nothing like carrying around multiple computer systems for a bitty little laptop on bitty little SD cards.