Outlook Client Not Connecting to Exchange on First Setup

Our users are still sending mail back and forth just fine and are able to use their existing setups just fine, however when firing up Outlook for the first time under a new user or an existing user under a profile on a different machine, we’re unable to get Outlook to communicate with the Exchange server. Exchange is 2007 and our Outlook clients are mixed 2007 and 2003.

The error states that Outlook cannot log on and to verify my network connection. I’ve done so, I can ping the mail server by it’s name, FQDN, and IP address, I can remotely access it, however I still can’t seem to get Outlook to hook up. I don’t what’s wrong, any ideas?