Email notifications - TLS

My companies SMTP server is on Microsoft Exchange Online which uses TLS authentication.  When I try to test the Email Notification with all of the fields filled in correctly I get:

5.7.1 Client was not authenticated Exchange 2010

I have run into this before and have usually found that, although SSL is working, the application doesn't us TLS.  

Here is a link to Microsoft's SMTP authentication for Microsoft Online for your reference:
http://www.microsoft.com/online/help/en-us/helphowto/be25e53b-c841-45aa-8bc5-a035e466d543.htm

Let me know if you need any more background, 

Did you check "Use SSL" checkbox on "Email" tab of the "Application Settings" dialog? This should also enable TLS. Also make sure you set SMTP authentication settings correctly on the same place.