After about 30 minutes of letting it sit connecting/disconnected, it finally connected. It must have some sort of time out period, but there has to be a way to flush this manually...

Bonus if you can tell me how to do it through Exchange Management Shell so I don't have to involve the admin :P