I am afraid the DNS seems to at fault. Have you already ceated a profile? If yes then try and create a new profile and let outlook to error out into message box where you can see the exchange connection field and username field.
If you are i the domain then in the exchnage server field you need to put the your server full dns name: server.domain
and then try to check the name of the username.
Let me know what you found