Outlook 2007 error message: "Must be online or connected to complete this action"

Hi,

I am running Exchange 2007 on a dedicated server in in a WMware lab with all
exchange roles on this one server. Connecting from any client using OWA
works fine. Also Outlook 2003 from an XP client work fine, but the problem
is when connecting from a Vista or XP client using Outlook 2007. The
Autodiscover feature recognises my exchange server name and mail address but
when establishing the connetion to the exchange server it prompts me for
account/password information. Supplying this with my normal account or even
using an enterprise admin account presents me with the following error:

"The connection to Microsoft Exchange is unavailable. Outlook must be online
or connected to complete this action"

I have searched event logs and the internet without finding the cause or
solution for this.

Anyone having a good explanation or solution would really make my day!
Thanks in advance!

Regards
Morten