Problems with adding network printers

I have a Windows 2003 domain with Active Directory and a Windows 2003 printserver. THe client computers are Windows XP SP2 (the firewall is disabled). The usual way to add a printer on a client computer on the network is; - starting "add printer wizard" - add network printer - "Find printer in the directory" - clicking "Find now" (without adding a name for the printer) - rightclicking a printer on the list and selecting "connect". This has always worked fine, but in the last couple of days some users are not able to add a printer this way and are getting the error message; "Window cannot connect to the printer. Either the printer name was typed incorrectly, or the specified printer has lost its connection to the server". They get the same message on all the network printers. The strange part is that if they try to open \\printservername\ (to open a windows with all the shares on the printserver), and rightclick the same printer on this list and select "connect" it works fine.. What is the difference ? This has always worked fine, and there has not been made any changes on the server or on the computers (these are not new computers). Please help me to fix this annoying problem... :)