For sufficiently large music collections, Rhythmbox can be a bit .. special.. when it comes to caching the index.
If you find you are having issues, I stand by this "Nuke it from Orbit" process:
As per StackOverflow:
- Close RhythmBox
- Delete the database cache file
- Set the default music folder
gsettings set org.gnome.rhythmbox.rhythmdb locations "['file:///dev/null']"
- Reopen RhythmBox
- Go directly to Edit > Preference > Music, and select the folder your files live in.
- Go go Music > Import
- Click 'Import'
The last step is important. I found I was waiting several hours for the database to be cached. Leave it alone. Don't try and play anything through it, just let it churn in the background.
After it's complete, you should have a useful music player again.