Da ich Clementine auch noch installiert habe ( 1.4.0rc1 ) habe ich mal geschaut. Bei mir konnte ich auch keine Visualisierungen wählen, es kam nur dies "M" von ProjectM. Die Suche hat mich dann von
Ubuntu zum
englischen Wikieintrag zu ProjectM geführt.
Leider lässt sich projectm-pulseaudio bei Clementine nicht einbinden, visualisiert aber alles was über pulseaudio läuft, bei mir auch mocp.
Edit: Eigenartigerweise ist projectm installiert, da eine Abhängigkeit von Clementine. Und im VLC funktioniert die Visualisierung damit. Dürfte also schon ein Bug sein.