Symptom: After changing the samAccountName (User Principal Name (UPN)) of a user in your on-premise Active Directory environment, run the DirSync tool to update the user on Office 365 (or wait 3 hours) [and have verified the user's new UPN synchronized in the Office 365 admin portal], the user is presented with the following error when trying to sign into Outlook, SharePoint, CRM, etc. on Office 365.

Sorry, but we're having trouble signing you in  Please try again in a few minutes.  If this doesn't work, you might want to contact your admin and report the following error: 80041034.

Solution: This turns out to be an issue with ADFS (Active Directory Federated Services), caching user account attributes, which prevents a successful login.  Here are a couple of solutions to solve this issue:

1. Try reupdating/repairing party trust with Office 365.
   1. Login to one of your ADFS servers.
   2. Click Start, All Programs, Windows Azure Active Directory, and then select Windows Azure Active Directory Module for Windows PowerShell.
   3. Execute the following command to connect to Microsoft's online services (when prompted, type in your Office 365 Administrator credentials)
      1. Connect-MSOLService
   4. Execute the following command to update federated trust
   5. Update-MSOLFederatedDomain –DomainName:<Federated Domain Name>
2. Try temporarily disabling Local Security Authority (LSA) credential caching on your AD FS servers (note this can increase the load on your ADFS and AD DS servers)
   1. Login to each of your ADFS servers and complete the following steps
      1. Click Start -> Run -> regedit to open up the registry editor
      2. 
      3. Navigate to the following registry key
         1. HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Lsa
            
            
      4. Right click on Lsa, select New -> DWORD (32-bit) Value
         
         
      5. Enter LsaLookupCacheMaxSize as the value name and press Enter
         
         
      6. Right click on LsaLookupCacheMaxSize and select Modify
         
         
      7. Ensure the value data is set to 0 and select OK
         
         
   2. Verify the user can successfully login.  Once they can, continue on to delete the key we created
   3. Right click on the LsaLookupCacheMaxSize value we created and select Delete
      
      
3. Reboot all ADFS and ADFS proxy servers in your environment

Microsoft has released an official KB article referencing this issue, you can find it here: http://support.microsoft.com/kb/2535191