For us, we've eventually tracked the cause down to an invalid folder redirect in GPO > User > Preferences > Windows Settings > Registry. We are redirecting the Camera Roll via registry key, and this was set to a location the users couldn't access or no longer existed. No errors for this were being shown in the event logs and folder redirection was all showing successful, so we weren't getting any clues as to what the problem was.
Why an errant folder redirect would break folder renaming across the board is anyone's guess!