I did what Nicolod suggested and it worked. Just grab any song in a playlist, drag it up or down, and then release it. It causes the google music app to realize it needs to re-sync and then your phone should re-sync if you refresh it or have it on auto-sync and automatically add the entire playlist to your phone.