No, clementine is a Qt app.
And it uses gstreamer-0_10, so you need the gstreamer-0_10 plugins, gstreamer-0_10-fluendo-mp3 (from repo-non-oss) and/or gstreamer-0_10-plugins-ugly-orig-addon (from Packman) for mp3 support in particular. (I already wrote the same thing in another thread today…)
Those should be part of both installers though, the one for GNOME and the one for KDE IIRC.
Well, I think the codec installers never installed the fluendo codec, as this is installed by default anyway.
But on 13.2 only gstreamer-fluendo-mp3, i.e. the mp3 codec for gstreamer 1.0, is installed by default, because most applications use that now anyway (even KDE, by default at least).
But as said, clementine in particular still uses gstreamer-0_10, so you have to install that one manually.
The KDE installer should install gstreamer-0_10-plugins-ugly-orig-addons (at least up to 13.1, not sure if they have been adapted to the change in KDE to use gstreamer-1.0 or not).