You guys who are having the problem, have you got lots of references to each song? Say, one in an Artists playlist, one in Artist/Album, one in Genre, and so on?

Possibly. I'll delete some playlists to see if that fixes it.

Thanks.