If you know the IP address of the printer, try doing a continuous ping to it in the command prompt (ex: ping 192.168.1.105 -t ) or in the Terminal.
While running the ping test, check to see if the printer stops pinging. Also send a print job to it to see if pinging the printer (with responses) results in an immediate print. If the printer takes 30-40 seconds to start printing, at which time it is not responding to pings, it sounds like the printer may be losing wireless connectivity or has another, deeper problem affecting it.
A while back, I upgraded a buddy's router using an old router of mine. His old router was a Linksys BEFSX41v1, which was having difficulty maintaining more than 10Mbps from the Internet to his network on his cable connection. The replacement was my old Linksys WRT54GXv1 (wireless disabled, as it was dead, which is why I quit using it), which handles the connection like a piece of cake. He had an HP Printer at the time of doing that upgrade wirelessly connected to an access point on the second floor of his home. With the old router, the printer worked fine. With the new router, even though the printer maintained a wireless connection to the access point, it would stop pinging after 10-15 minutes from a reboot. I suspect this had to do with "ARP Table" issues by the replacement router, that stopped the printer from being rachable, as none of the wireless settings had changed. To resolve, I had to wire up the printer to a nearby network jack, then disable wireless, at which point it worked flawlessly on his network.
While the printer was down to ping, it would not print a single document. Once it came up to ping, any documents sitting in the printer's queue on any computer would immediately be received by the printer, and it would start printing. The printer would then go down to ping a few minutes after printing again for an undetermined amount of time.
Just some food for thought.
