Network printer not displaying in directory.

I recently installed two ethernet attached network printers on a dedicated print server running Windows Server 2003. Both printers are shared and proper rights have been given to all users. When trying to install them on workstations by searching the directory the printers are not displayed. I made sure the check box to have them added to the directory is checked. I am able to ping both printers and access their web configuration pages. I can install the printers on a machine if I specify the name instead of searching for them. Anyone know what might cause this?