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:``
…it just removes the database file.
* I’m using Rhythmbox 0.10.1 on Debian Sid.