At the risk of going out on a limb (I use Samba, but I’m not an expert) let me suggest a few things.
From the command line (Shell prompt) on the Linux machine, do a “nmblookup -A IPADDRESS” where the IPADDRESS is that of the NT machine. (nmblookup is the equivalent of the nbtstat on a windows machine)
Then do the same thing for the W2K systems for which printing does work, and see if you can identify any differences in the NetBIOS names presented. This might offer a clue.
Also, have you checked the /etc/printcap and the .config file in the /var/spool/printdir where printdir refers to the sharename of the printer specified in the printcap file?
Sorry I can’t offer more. Good luck,