This didn't work for me, exactly, but it did help me to isolate at least one aspect of the bug.
I followed explicitbunny's directions. I cleared all the music on my phone through Settings as well as from the Music app. When I synced with my desktop, I ended up losing all my playlists on both devices because Apple software is a hot mess. Infuriating. Then I tried an experiment, based on the observation noted here that the duplicate playlist has fewer songs, and is in fact the previous version of the playlist you've added songs to. So I created a small playlist. Synced my phone. Added a few songs to the playlist and synced again -- another duplicate playlist. Darn!
BUT... I also noticed that an album (that I had bought through iTunes/Apple music) magically reappeared in the Music app on my phone, even though I had not selected it from my desktop. Weird. I deleted this from my phone and tried the experiment again. Still no success. Then I went ahead and deleted that album from iTunes on my *desktop* (figuring I could re-download it from the cloud at another time). BINGO!
Now, I'd had this duplication problem before I'd purchased this particular album, and found the only solution was to restore my phone, though even that "fix" was temporary. I'm reluctant to suggest that anyone go ahead and risk losing all their carefully collected playlists to corroborate my findings, but I am curious if anyone else has had a similar experience. In any case, the fact that iTunes wanted to put some "unselected" album in the Music on my iPhone seems to suggest that the root of the problem lies in iTunes rather than the iOS.
iPhone 6S+ // i Mac // OSX 10.11.6 // iTunes 12.4.3.1