I'm guessing that you use Windows Vista. We had this problem on Vista but not on XP.
From Microsoft: In Windows Vista, Internet Explorer uses the Web Client service when you use Internet Explorer to access a WebDAV resource. The Web Client Service uses Windows HTTP Services (WinHTTP) to perform the network I/O to the remote host. WinHTTP sends user credentials only in response to requests that occur on a local intranet site. However, WinHTTP does not check the security zone settings in Internet Explorer to determine whether a Web site is in a zone that lets credentials be sent automatically.
If no proxy is configured, WinHTTP sends credentials only to local intranet sites.
Note If the URL contains no period in the server’s name, such as in the following example, the server is assumed to be on a local intranet site:
http://sharepoint/davshare
If the URL contains periods, the server is assumed to be on the Internet. The periods indicate that you use an FQDN address. Therefore, no credentials are automatically sent to this server unless a proxy is configured and unless this server is indicated for proxy bypass.
This is a known issue that has not quite been completely fixed yet. There is a MSDN blog about it here: http://blogs.msdn.com/sharepoint/archive/2007/10/19/known-issue-office-2007-on-windows-vista-prompts-for-user-credentials-when-opening-documents-in-a-sharepoint-2007-site.aspx
There is an interesting workaround posted here: http://grounding.co.za/blogs/neil/archive/2008/11/10/workaround-sharepoint-keeps-prompting-for-login-when-creating-office-2007-documents-on-vista.aspx
Ultimately there is a patch that has been included with Vista SP1 but it also requires a registry edit. We just recently got this to work using the following steps on a Windows Vista SP2 client:
Open regedit. Navigate to the following subkey:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\WebClient\Parameters
Create a new Multi-String value called AuthForwardServerList and give it a value of (for example):
https://.Contoso.com
http://.dns.live.com
*.microsoft.com
https://172.169.4.6
Then restart the WebClient service.