After you have verified you can see the Autodiscover cname record on http://tools.appriver.com/DnsLookup.aspx you may want to make sure you see the record from your network.
Open Command prompt:
Open the Command Prompt window by clicking the Start button , clicking All Programs, clicking Accessories, and then clicking Command Prompt.
Click the Start button, In the Search box, type Command Prompt, and then, in the list of results, double-click Command Prompt
Just hold down the Shift key and right-click on blank space on your desktop and choose “Open Command Window Here”.
Type: ping autodiscover.yourdomainname.com
if correct it will say Pinging autodiscover-namsouth.outlook.com [18.104.22.168] with ... (this IP address may vary)
Request timed out. (This response is OK)
This test will ensure you can see the record from your network.