I had this problem recently, where every song I had ever purchased from the itunes store had the dotted circle next to it on my new iPhone5. I was syncing from iTunes on a Mac Mini. I tried the many things suggested including:
1. Turning off "sync music", applying and turning it back on
2. Turning off "wifi sync"
3. Signing out of Apple Account on both devices
4. Make a backup, restore, then setup as new device, then restore backup.
5. Deauthorize, then reauthorize my computer
None of this worked, but after thinking about it - I used a combination of 1 and 4 which worked for me as follows:
1. I turned off "sync music", and applied - removing all music from the iphone.
2. I created a new backup (which has no music).
3. I restored the phone to factory settings, setting it up in iTunes as a new phone.
4. Then restored it from the backup previously created.
5. Once restored I then rechecked the "sync music" checkbox, applied changes, and watched all my selected music copy accross perfectly.
I'm not even sure you need to set it up as a new phone TBH, you can probably restore it straight from the backup once it's restored now it has no music saved in it. If you do set it up as new phone, this makes a newer backup than the one you want to use, so don't take iTunes advice to "use a newer backup".