Have a look at the Sandisk Sansa, i've just got an e270 (6GB) which is great, its a little bigger than the Nano but doesn't need any software to put music onto it as it's just drag and drop
The 4GB one should hold around 1K tracks depending on compression and is around the same price as the 2GB Nano
expansys do them at a resonable cost, about 112quid