Clementine is a multiplatform music player. It is inspired by Amarok 1.4, focusing on a fast and easy-to-use interface for searching and playing your music.
It works awesome on all platforms but in Gnome Shell it have bug with notification system in gnome shell, this cause that notification is not showed when song changes.
To fix this go to Clementine Preferences, navigate to Notifications and un-check "Include album art in the notification"
Now notification will show.