Free/Busy lookups from Notes to Office 365 fail and logs show a 401 error (4300939)

Free/Busy lookups from Notes to Office 365 fail and Coexistence Manager for Notes (CMN) Freebusy logs show that CMN was set to use  https://autodiscover-s.outlook.com/autodiscover/autodiscover.xml fot the endpoint that it needs to connect to for the customer's Office 365 Tennant:
2013-06-26 15:49:34,179 [21] INFO  AutodiscoverWorker - Using hint autodiscover address https://autodiscover-s.outlook.com/autodiscover/autodiscover.xml
2013-06-26 15:49:34,179 [21] INFO  AutodiscoverWorker - Email address: firstname.lastname@domain.onmicrosoft.com
2013-06-26 15:49:34,179 [21] INFO  AutodiscoverWorker - EnableScpLookup:False
2013-06-26 15:49:34,694 [19] INFO  ExchangeFreeBusyConnector - Initialize() Enter
2013-06-26 15:49:34,694 [19] INFO  ExchangeConfiguration - User name credential is AdminAccount@domain.onmicrosoft.com

The logs then show the 401 error:

2013-06-26 15:49:34,694 [19] ERROR FreeBusyWcfServiceBase - GetFreeBusyInfo()System.Exception: Invalid email format from Free/Busy request  at QuestSoftware.CMX.API.Core.FreeBusyConnector.WcfServiceHost.FreeBusyWcfServiceBase.ApplyMappings(SmtpEmailList& emailCollection) at QuestSoftware.CMX.API.Core.FreeBusyConnector.WcfServiceHost.FreeBusyWcfServiceBase.GetFreeBusyInfo(SmtpEmailList smtpEmailList, DateTime startDateTime, DateTime endDateTime)

2013-06-26 15:49:35,131 [21] ERROR AutodiscoverWorker - System.Net.WebException: The remote server returned an error: (401) Unauthorized.