We redirect My Documents to their Z: (personal) drive, and Desktop and Favorites to folders on their Z: drive. It's all done via GPO.
Switching to such a Policy shouldn't be that difficult. When setting up redirection, GPO (at least for Server 2003) should prompt you to move to data from the old location. Just have all users log off the evening you make the change.
Test a couple of users manually after the change is made and adequate time is allowed for the GPO to propogate. At worst, your Helpdesk sees a short-term upswing in phone calls when things are missing. The Helpdesk runs a quick copy, and they are back in business.