First some mad props to Exchange Genie for getting the info on this out 2 years ago…
I saw this issue popup recently with a Windows 2008 server with the CAS role installed. Advanced security on Windows 2008 helps prevent NTLM man in the middle and “reflection attacks” by blocking access when the FQDN or custom hostname of the resource you’re trying to access is different from the computer name.
I recommend working around this by running the commandlet from an Exchange Command Shell that doesn’t have the CAS role. In an All In One topology, install the Exchange Command Shell on a workstation. The other option is to follow the steps in those support articles but weigh carefully the risk in making the server vulnerable to the attacks mentioned.