Все ваши настройки сохранены в файле ~/.gconf/apps/rhythmbox/.
Вам нужно удалить этот каталог в Nautilus, нажать Ctrl + H, чтобы отображать скрытые файлы, а затем удалить его.
Внимание: резервное копирование этого каталога перед удалением.