Are these printers going to a queue on the server or are you printing to them directly? Have you tried setting them up to print directly to the printer (straight to the HP Jetdirect server orw whatever) and not go through the queue or vice versa? I have also seen the print dialog hang for minutes when the printer is a network queue and the print server machine is down. Never have seen this when you set the machines up to print directly to the networked printer.