Eu sei que isso é incrivelmente antigo, mas eu me deparo com o mesmo problema e não onde tem uma resposta de qualquer tipo. Para corrigir este problema eu instalei
sudo apt-get install libao-ocaml-dev
e isso parece ter resolvido o meu problema.
Meus sintomas eram que eu poderia tocar música se eu fosse root, mas seria o erro descrito pelo OP se eu não fosse. Eu precisava compilar o cmus a partir do código-fonte porque a versão do cmus que obtinha do apt não conseguia reproduzir algumas das minhas músicas devido a um problema de ffmpeg / avconv.
Eu não precisei fazer nada especial além de instalar essa biblioteca.