HTTP 400 Bad Request

When connecting to our web server (IIS 6.0, Windows 2003 Server), we have
some users that can only connect via IP address. When they attempt to
connect using the servername, they receive a HTTP 400 Bad Request error. We
have verified that DNS is correct and that it's not a permission issue (or at
least we think it's not permission since they can connect via IP address).
All clients are using IE. There did not appear to be any logs generated on
the server. A sniff of the traffic did show that the request was making it
to the server.

Here's a overview of what we are seeing for two users on the same machine.

User A logs in.
-Can access the web site using the hostname
-Can access the web site using IP address
-Using WFetch generates a HTTP 400 Bad Request error

User B logs in.
-Cannot access the website using the hostname
-Can access the website using the IP address
-Using WFetch generates a HTTP 400 Bad Request error

Has anyone seen this type of problem?

Thanks for your help.