I had this issue with Rhapsody getting hosed on my new Fuze+ every day or two. It’s been 2 weeks so far without the issue. All I’ve done differently is to never plug the Fuze+ into power or the computer while it’s turned off. I always turn it on first, then plug it in.
I’d be interested to see if this works for others. If it does, maybe it’s a clue for SanDisk to investigate the cause of the problem.