Crazy idea: Try rebuilding the database.

Corollary question: How many tracks on this player? What do the tags look like, are they pretty clean? (i.e., tons of information in the "comment" field of every tag for example?)

Player version number?