Access Denied when connecting to Office 365 using Powershell

The other day I had a really annoying, tear-your-hair-out kind of problem with using Powershell to Administer Office 365. I had an administrative user account called CogmotiveReports@mycompany.onmicrosoft.com but every time I tried to log on to Office 365 using Powershell it through an Access Denied error like this:

WARNING: Your connection has been redirected to the following URI: "https://pod51031psh.outlook.com/PowerShell-LiveID?PSVersion=2.0 "
[pod51014psh.outlook.com] Connecting to remote server failed with the following error message : Access is denied. For more information, see the about_Remote_Troubleshooting Help topic.
    + CategoryInfo          : OpenError: (System.Manageme....RemoteRunspace:RemoteRunspace) [], PSRemotingTransportException
    + FullyQualifiedErrorId : PSSessionOpenFailed
Import-PSSession : Cannot validate argument on parameter 'Session'. The argument is null. Supply a non-null argument and try the command again.
At C:\connect-ps.ps1:5 char:22
+ Import-PSSession <<<<  $Session
    + CategoryInfo          : InvalidData: (:) [Import-PSSession], ParameterBindingValidationException
    + FullyQualifiedErrorId : ParameterArgumentValidationError,Microsoft.PowerShell.Commands.ImportPSSessionCommand

I could log into the Microsoft Office portal without any problems, so it wasn't a permissions or username and password error.
A lot of Googling later I came across a Microsoft Office 365 community forum thread where someone else had the same problem. They had found a solution to the problem, which was to change the UPN. I changed my UPN to CogmotiveReports@domain.com and it worked first time!
When I changed the UPN back to CogmotiveReports@mycompany.onmicrosoft.com it stopped working again. What a pain!
So, we have a work around - but it didn't help me work out why I had the problem in the first place. I did some more digging and troubleshooting and came across the MSOL Deleted Users section. I found the same account in the MSOL User Recycle Bin. I had totally forgotten that I had deleted this account a week ago and re-created it with the same UPN.

PS C:\> Get-MsolUser -ReturnDeletedUsers
UserPrincipalName                       DisplayName                             isLicensed
-----------------                       -----------                             ----------
CogmotiveReports@alantest3.onmicroso... Service Account for Cogmotive Reports   False

I force removed the deleted user in Powershell and verified that it no longer came up when I ran the Get-MSOLUser -ReturnDeletedItems cmdlet.

PS C:\> Remove-MsolUser -UserPrincipalName CogmotiveReports@alantest3.onmicrosoft.com -RemoveFromRecycleBin
Confirm
Continue with this operation?
[Y] Yes  [N] No  [S] Suspend  [?] Help (default is "Y"): y
PS C:\> Get-MsolUser -ReturnDeletedUsers
PS C:\>

Now the account works perfectly.