Easy fix (usually). Probably in the FAQ, too!

Essentially, you have to connect up the serial cable, hit 'q' to quit the player, remount the music partition(s) rw, delete the database files, and then start the player from the command line. It will rebuild the databases then, and after that finished you kill it again, remount the music partitions r/o, and exit the shell.

Check the FAQ for more info.

Cheers