russellskanne: You should give the Sansa Clip (especially Clip +) another chance. I think it's the best you can get in terms of price, simplicity (no video etc.), supported audio files (ogg, flac etc), battery life (>10h) and disk space (-> microSD slot). And the best thing: you can rockbox it:
http://www.rockbox.org/ (better responsiveness, tons of options, plugins (you can play doom on it, seriously), better filesystem and playlist support etc.; maybe it would also resolve the clicking problem for you).
I know, i don't regret buying mine since it worked like wonders for the past 3 years but i just hate the clicking noise (i'll explain below) and the cheap build.
RadonGOG: Clicking noice?! Never had such a problem on my one. Why don´t you just return it if you have such unordinary problems with it?
Wish you much luck! :)
It's not a clicking noise from the music/sound, it's from the plastic button when changing tracks, you can hear it
here.
akhliber: I highly recommend one of FiiO's audio players. I currently have a FiiO X5 high definition audio player and I'm in love with it. They recently released the X1, which is only $99-$150, depending on store / promo and such, and plays mp3's and lossless audio to boot (note, though, that it has no internal memory, but that it takes one micro-sd card, currently up to 128gb)
http://www.fiio.net/en/products/18 Uhm, this looks interesting but a little expensive considering that it doesn't even has internal memory (i'm aware that it has a mini sd card slot but so does the sansa clip and that one it's cheaper AND with internal memory). Uhm, 130€ (with postage) is above of what i was expecting, dunno...