Cannot delete songs from iPhone
I finally fixed it by restoring from an iCloud backup. But I read that this does not seem to work for some users. 

I personally think, iTunes' quality is really bad and I'm tempted to move over to Amazon's music service but I love the Apple ecosystem and they probably have other issues. Sigh.