Use Microsoft's tool to check your
autodiscover record. Choose the "Microsoft Office Outlook Connectivity Tests". You will fail all except the last section when it specifically test your auto record - you should pass this and if not, it will help you figure out what is in error.
My Other suggestions: http://bit.ly/segoideas