Here's the setup - the Linux box was the domain controller, and it exposed a Workgroup to the Windows Network (under My Network Places -> Entire Network -> Microsoft Windows Network ->
I'll cut a long, exasperating and expletive-ridden story short, missing out all the entertaining cursing of various rude bits of various animals to various circles of hell, and jump straight to the end. Turns out the problem was that WinXP Home couldn't resolve the domain properly without an LMHOSTS file.
Pretty much everyone who's worked with Windows and the web for any length of time knows about the HOSTS file. This lives in (Windows Root)/System32/drivers/etc and is an extensionless file, mapping host names (e.g. myserver.mydomain.com) to IP addresses. Handy for those occasions when you need multiple domain names mapping to your own pc, for instance when you have a system serving multiple sites from one codebase resolving via the hostname.
The LMHOSTS file is similar, and lives in the same place, but is not quite as straightforward. Its purpose is to tell Windows how to resolve NetBios names, and the format is... well... non-trivial. Full information is here : How to Write an LMHOSTS File for Domain Validation and Other Name Resolution Issues
The important entries you'll need are:
10.0.0.1 PDCNAME #PRE #DOM:DOMAIN_NAME
10.0.0.1 "DOMAIN_NAME \0x1b" #PRE
Replace 10.0.0.1 with the IP address of the Linux domain controller
Replace PDCNAME with the hostname of the Linux domain controller
Replace DOMAIN_NAME with the name of the WORKGROUP
Now for the fiddly bit : on the second line, you need EXACTLY 20 characters between the quotes. Between your domain name and the \0x1b there must be spaces, exactly the right number of spaces, and nothing but spaces. The MS reference above gives more detail.
But once I'd created an extensionless file called lmhosts in the right place, with the right entries, and the right number of spaces, suddenly I could authenticate.
As for the more fundamental question of which person at Microsoft decided on that format of the lmhosts file, where he/she lives, and how to gain access to their bedroom undetected while armed with a large fish, I'll leave that as an exercise for the reader.