Yes, with Exch2007, I couldn't setup a new mail profile using Outlook and Autodiscover. I worked with a Microsoft Tech rep and once we unregistered the SPN on my Exch2007 server, the Autodiscover piece of setting up a new mail profile completed successfully. The KB article I used I listed above as basically, when I setup a new Outlook profile, I couldn't use "negotiate authentication" and had to use "NTLM authentication."
This is the same scenario I am seeing now with Exch2010. With a mailbox that's on Exch2010 server, I can't setup a new Outlook profile and have Autodiscover successfully finish. I am continually prompted for a username/password. I also can't contact the OOF and AS service if I manually create a new Outlook profile. This was exactly the same with Exch2007 and once I unregistered the SPN, these issues went away with Microsoft Tech rep.
With a mailbox that's still on Exch2007, the new Outlook profile and mailbox setup completes successfully using Autodiscover. This is has been tested with Outlook 2007 and 2010 with the same results so I know it's an Exchange 2010 config issue.