I have a Sansa c250 currently running build 15647-07. I had the immediately previous build and encountered the same problem.
The database will not succesfully initialize. If I delete the .tcd file and try initializing the database, it will say "Building database..... Found ### files" (where ### is much greater than the number of music files I have). Then it will say I should reboot to enable the database. However, when I reboot, the database says it has not been initialized and attempts to reinitialize the database. This time, however, it says "Building database..... 0 files found."
This problem occurs irrespective of where my music files are located. I checked my ID3 tags, and didn't notice anything untoward (as has been suggested previously).
Doing a clean reinstall of Rockbox (to the version I am currently using) had no effect either.
Help please?