I’m having this same exact problem. It works fine until i turn off my Sansa Clip + 4GB. When I power it on again, it tells me to synchronize with my PC.
I have done the following at least twice at this point:
1. checked date of my pc and sansa clip+
deauthorized, reauthorized my pc and device numerous times.
licensed the tracks countless times
reset the secure clock several times
formatted the device through rhapsody, through windows media player, through my pc, and through the device.
checked for firmware updates with sansa updater
checked my account settings/e-mail in rhapsody and on my device (they match)
installed rhapsody 4, uninstalled it and re-installed it.
I have been a rhapsody to go member for at least two years at this point. This is my 2nd Sansa mp3 player. I just bought this one this past August, so it is fairly new. Please help!! I have been in contact with rhapsody as well, and they have no other fixes for me!