Getting an Error when Migrating Mailboxes to 0365 in a Hybrid Setup

Recently I was moving a couple mailboxes to O365 when I get an error. The error itself was pretty unhelpful as all it said was that the connection could not be completed.
This was working fine last week, what gives?

I started out troubleshooting by jumping into PowerShell and running the Test-MigrationServerAvailability to try and get a better idea of what was going on. This should be your go to command when you have an issue as the generic error is supremely unhelpful.
Running the command I got an "Access Denied" in the error output.
 Hmmm, so I'm getting an Access Denied when trying to hit the MRSproxy.svc URL, interesting.
In Exchange I've leared over the years that when you get an access denied error, go check the permissions in AD. The MRS proxy uses the computer account of the Exchange server so I checked that, and the groups looked fine but when I looked at the attributes you can see the admincount was set to 1. Bingo that's a problem since it will get the protected admin acl, and Exchange does most of it's perms through inherited permissions. Looking into it one of the Exchange groups was mistakenly added to the Builtin\administrators group in the domain.

There's a MS KB article on this too:
I removed the group from the administrators, cleared the admincount flag on the group, and enabled inheritable permissions. I then had to clear the admincount and enable inheritance on each of the Exchange server computer objects since the were all members of the misconfigured group.
Last thing to do is restart the server and then try to move the mailbox again.
At this point I'm thinking I'm golden, I found the problem and fixed it. I run the Test-MigrationServerAvailability again and get a Success!
This is great! Now I go to migrate the mailbox to O365 and BAM!!
What gives?!
Now I know that the permissions are right and when I run the test I get a success but if I actually try to do a migration it blows up. After thinking about it for a few I thought to check the migration endpoints. The Migration Endpoint has an associated admin account. The account it is using has recently had the password changed. I pop in the new password and save the changes. Don't forget that there's an Endpoint on Prem and an Endpoint in O365 also, change them both!

Now I go back select the mailbox that started all this and try to migrate it to O365.

Now I can add the normal required information and off the mailbox goes to the cloud!

Moral of this story is that sometimes fixing one problem leads you to another, just keep following the bread crumbs. Always remember to check that pesky admincount when you get a strange permission or access denied error in Exchange, and always make sure to check the accounts and passwords that are actually performing the process!