I have a continuing problem however - the playlists are completely hosed.

Unless you're having problems with the disk drives or the cable connections, your playlists should not be hosed after rebuilding the database. Please check this problem and this problem.