Did you change the Profile field of the user as well? I'm not sure, but it may do the trick.
I suggest you use the following sequence:
- Add a new profile link
- Set the user's Profile field to the profile id you just linked.
- Remove the link to the 'old' profile
Hope this helps,