These are the steps I took to resolve the issue. I was particularly concerned about users losing saved messages in their voicemail. The posted solution did not give much detail on what to do.

1) Create a new user in CUCM. For example, I have a user called 'John Doe' in the system. I created a new one called 'John Doe2'.

2) After creating the user I associated 'John Doe2' to the phone in use by 'John Doe'. Then I set the Primary Extension as needed for that user. Hit the 'Save' button and verify that the 'Create Cisco Unity User' option shows up in the drop-down box in the right hand corner.

3) Log into Cisco Unity Connection Administration, and select 'John Doe'. Click on the link to re-associate and select 'John Doe2'. This links the Unity user to the CUCM user.

4) Log back into CUCM and select 'John Doe' from the user list. Remove all device associations from the user. Hit Save, then delete the user.

5) Select 'John Doe2' and rename the user as 'John Doe'.

These steps fixed my problem. I had to do it for all the users whose association was broken. One note to make is that the voicemail PIN is automatically reset to the default I believe, which is 0000. Other than that voicemail continues to work normally and users don't have to redo their greetings and such.