I just got a new Rio Karma MP3 player to replace my Nomad Jukebox 3, which I unfortunately broke recently. I've been very impressed by the Karma's size, functionality, sound, and battery life. There's also a nice user community on the web to tip you off to firmware updates, tips and tricks, etc. If you're looking for a large capacity MP3 player and don't want to pay the premium for an iPod, I highly recommend the Karma. I found a good deal on PriceGrabber.
Another unfortunate thing about my old Jukebox is the software for transferring files from it doesn't write back the ID3 tags when you move an MP3 to your computer. Luckily, others have had to deal with this problem; this command-line tool looks like it will fix things up nicely.