Por favor, nos dê a saída de dpkg --get-selections | grep -i flac
para que possamos ver se você instalou as bibliotecas corretas ou não.
Para referência, estou executando o Ubuntu Precise e tenho:
me~banshee:~$ dpkg --get-selections | grep flac
flac install
libflac8 install
libflac8:i386 install
... e o Rhythmbox toca muito bem para mim.