What authentication method are you using, and what SP/patch level on
both server and client?

I've seen this in the past in MOSS 2007 if the Service Pack level of the
server didn't match the service pack level of Office on the client. Double
check what build number you are at on the server and what build number you
are at in office on the client. If you are using Office 2007 on the client
and SharePoint Foundation 2010 then you should make sure that Office is up
to the latest Service Pack available for Office.

We've seen this. Have you tried "Repair"ing the Office install on the client?

I have, though not in this situation.

Turns out the guy in charge of this was using a Chris Givens setup; he
determined that there was something wrong with it, subsequently dumped it
and built his own, and it's working. I haven't had five minutes to ask
after it further, but it's working now.

Thanks for the responses, everyone; I shall take them under consideration
for the future.