Eu pareço ter conseguido consertar isso. Eu não entendo bem o que eu fiz, porque eu limpei o cache antes, mas eu acho que quando eu tentei parar antes, ele não me deu ouvidos. De qualquer forma, talvez seja minha imaginação, mas parece que a qualidade do áudio está um pouco pior depois de fazer isso:
Esta é uma adaptação do link
$ pkill -STOP '^pulseaudio$'
$ rm -rf ~/.pulse
$ mkdir -p ~/.pulse
$ echo 'autospawn = no' >~/.pulse/client.conf
$ pkill -KILL '^pulseaudio$'
E então eu apenas abri o spotify e as coisas pareciam funcionar novamente. Espero que isso não seja apenas temporário.