I think Patrick is really close on this one. We had the same problem. we are all in a 2003 domain. Heres what we did:
From IE:
Tools > Internet options > Security tab > custom level
then scroll all the way down to ''User authentication'' - ''Login''
then activate ''automatic logon with current username and password''
ok,ok,ok,ok
Now ...