So sure enough I deleted a handful of the albums I'm least likely to listen to, and now it's working again. Thanks very much for your help peter, although I can't help but wonder now how many more songs I can fit on there before i reach that limit again.

Just out of interest, the only way around this would be a memory upgrade correct? What is the story with the database with ID3 tags? If I prune all the comments and garbage out of them, will that shrink the database? Does the empeg use ID3v1 or v2 or both to generate the database? If this is all in the FAQ I apologise, I did have a read through to try and fix the problem, but I don't recall seeing any of this information here.