
From the rekordbox "Read Me" thread...
Go to:
XP: C:\Documents and Settings\yourusername\Application Data\Pioneer\rekordbox
Vista: C:\Users\yourusername\AppData\Roaming\Pioneer\rekordbox
Win 7: C:\Users\yourusername\AppData\Roaming\Pioneer\rekordbox
OSX: /Users/yourusername/Library/Pioneer/rekordbox
Rename datafile.edb to datafile.edb.old
Rename datafile.backup.edb to datafile.edb (removing .backup)
Try again.