I am also having this issue on Windows 7, although I found the delay can be anywhere from 15 minutes to several days. There is no discernible pattern as to when the document eventually prints. Sometimes it prints right after another machine is logged on to the network. Sometimes it will print when the computers are idle after everyone has left the room. Sometimes it prints when I power up the next morning. It's really baffling and rather annoying. If my wife needs something printed "right now", my only recourse is to print from the computer the printer is attached to. Local printing is always instantaneous.
Network connectivity between the machines is well-established and well-tested at gigabit speeds. Printer is on, not off or in standby mode, and is connected to the computer via USB. It should just work, but it doesn't.