I’ve installed Clementine to look into this and I can confirm that it does not behave as it should. I suspect that it’s hard-coded to use the big icon it installs in /usr/share/pixmaps and not follow the icon theme, in which case there’s not much to do.
There’s a general issue with the indicators area used by MATE, Clementine isn’t the only software that displays a big icon when no proper one is available in the icon theme.
EDIT: after a few tests, I’m beginning to think that the icon is embedded in Clementine itself and doesn’t use the ones installed in proper places. Also, the Ubuntu Mono themes, which Ambiant and Radiant MATE use, has a Clementine panel icon, so if it would work properly, it should with the default MATE theme (my 99.99% assumption from above was wrong).