It can't be a domain if it's Windows XP on all machines, unless you have a server (2000 or 2003).
I've had trouble like that (Windows 2000 domain) and it was partly to do with users' rights. This probably isn't the case for you though, but the way I managed to connect to the printer in the end was just click Start > Run and actually type the UNC path to the printer:
It would then either ask me to install it (and do it) or just open the window and it would be there installed.
Might work for you.