It didn’t take long before I found a problem with Rhythmbox.* It couldn’t figure out the MIME type for half of Blonde Redhead’s newest album 23 (download it from emusic).
The simple fix was: rm -R ~/.gnome2/rhythmbox
This deletes your playlists and Rhythmbox’s database which is kind of annoying, but upon starting Rhythmbox is happily re-indexed all of my music automatically.
This command might work just as well:
rm ~/.gnome2/rhythmbox/rhythmdb.xml
…it just removes the database file.
* I’m using Rhythmbox 0.10.1 on Debian Sid.