ADFS - Salesforce SSO: UPN Change

I am having an issue with single sign-on using Active Directory Federation Services 2.0. Recently one of our users needed his User-Principal Name changed in Active Directory, which is the mapping used in Federation Services against the Federation ID in Salesforce. Active Directory was updated with the new User-Principal Name and I updated the Federation ID on the user record to match the new User-Principal Name. Unfortunately now when attempting single sign-on, I get a login error (the message I've gotten when there is no Federation ID for the User-Principal Id passed).

Does anyone know exactly how ADFS extracts data from Active Directory? Does something need to be restarted or a domain controller need to be rebooted to register this change?