OK, consegui que funcionasse excluindo as seguintes pastas:
~/.local/share/nautilus
~/.config
~/.gconf
~/.gnome2
~/.gnome2_private
É possível que eu precise excluir apenas uma ou duas dessas pastas, mas, ei, funcionou!
Eu só preciso abrir dconf-editor
novamente e redefinir minhas configurações do Rhythmbox e configurar o Ubuntu One novamente, mas ainda assim, tenho meus ícones de música de volta.
Certifique-se de saber o que está fazendo se quiser tentar isso também!