Just an update. I'm still getting this error. I have an 8gb clip and a 4gb sd card, both have over 100mb space left in each error. Still getting this error message when trying to create a playlist. The only time it hasn't done it to me is when all my songs are in one area (such as the 16gb sd card which i also have). So i dont think its a space thing, but rather an issue with music stored on both areas.
Hmm.. i dunno. Any body else had this error message?