If you’re frustrated by the fact that Clementine refuses to change it’s icon, here’s how to fix it:
- Locate the icon you want Clementine to use (make sure it’s in all the sizes you need)
- Rename them to “application-x-clementine” (without the quotes)
- Navigate to /usr/share/icons/YOUR_ICON_THEME
- Move your desired icons into their respective folders (e.g. move the 16×16 icon into the apps folder of 16×16 icons)
- Change your icon theme to a different one, and then change back
- Voila! Clementine should now be using your desired icons.
Optional:
If you want to change the tray icon as well, here’s how to do it:
- Locate your desired icons (if you want to use the Ubuntu mono-color icons [which I recommend], the download links are here and here)
- Resize them to 24×24
- Rename them to clementine-panel and clementine-panel-grey
- Navigate to /usr/share/icons/YOUR_ICON_THEME
- Go to the 24×24 apps folder (location will vary based on your icon theme)
- Move your icons into the folder
- Quit Clementine and open it up again
That should do it, if you have any questions, comments, or concerns, feel free to leave them below!
~Insert_Title~ 
