Exchange 2007 Autodiscover authentication issues...

I had just finished migrating our user base to a new Exchange server running Exchange 2007 SP1 on a 2008 R2 server. All went well except that the users running Outlook 2007 or higher kept receiving certificate errors. After a bit of research, I employed the solution which was outlined in the article below:

http://www.shudnow.net/2007/08/10/outlook-2007-certificate-error/

While this did correct the certificate error, it caused all Outlook 2007 and above clients to continually receive a password prompt.

In our scenario, here's how it looks:

Server NetBIOS name: mail2
FQDN in Active DIrectory mail2.SOMEADDOMAIN
FQDN External: mail.somedomain.com

When I access the autodiscover service via mail2 or mail.SOMEADDOMAIN (https://mail2/Autodiscover/Autodiscover.xml), it prompts me for my credentials, which I provide and then it lets me through. However, if I access the service via https://mail.somedomain.com/Autodiscover/Autodiscover.xml, it will continually prompt me for my credentials and never let me through. I am not sure why this is happening, but I really need some help. I was not able to find this specific issue online which is why I am asking your assistance. Can someone please provide a solution?

Thank you all so much!