If I were you I would probably try in the order of which is quickest. So...
Try the method in the link first, it's quick and you don't have to copy anything back to your phone.
If that doesn't work try erasing all your music from your phone by Settings > General > Storage & iCloud Usage > Manage Storage > Music > Edit and then delete all songs. You will have to copy your music back to your iPhone.
Third option. Backup your phone to iTunes. Then try a whole phone erase when you're plugged into iTunes, then restore it off the backup you just made. In this case you might end up restoring corruption from your backup.
The final option which would take the longest is completely erase your iPhone. Don't restore from backup and just set it up as if it was a brand new phone. You will have to re-enter all your personal settings, re-copy your music, everything.
As a last resort the final option should work but it's a pain in the backside.