Outlook says .. Microsoft Exchange is not available

This was is a good one and has been doing my head in!

I had a user mailbox that could log in to OWA but not Outlook.

With outlook you would get an error saying:

"Cannot open your default e-mail folders. Microsoft Exchange is not available. Ether there are network problems or the exchange Computer is down for maintenance"

If you run:

Get-LogonStatistics -Identity <email address>

Then have a look at the FullMailboxDirectoryName

This should match the users legacyexchangedn.  In my case, another user has the same address as a proxy address.

Just removed it and everything worked fine!