If you have had this problem, hopefully this post will save you some time. Take note that this will completely erase your library and the configured locations in Rhythmbox. It will not erase any actual music though.
rm -rf ~/.local/share/rhythmbox/*
Once you enter this command you can then open Rhythmbox as if it were a fresh install and setup new library locations at which point it will do a first time scan on them.