This is the article that pointed out the problem to me:
http://askubuntu.com/questions/65099/clementine-has-high-cpu-usage-even-after-shutting-it-down
Effectively you use the following command to start Clementine.
Exec=env __GL_NO_DSO_FINALIZER=1 clementine
Now we don't want to have to type in this line every time we want to start the app up, in KDE it's quite simple, just right click on the start button and select Edit Applications, find Clementine and replace Clementine &U with the above line.
Simples