Are you using an AEBS/Time Capsule by chance? I have been helping someone troubleshoot the same problem, with an officejet 8500, in addition to a few other network things acting flaky. Its a new 4th gen time capsule that was just added. I started over and redid the network, no change. switched printer from wireless to USB, no change. switched printer to wired ethernet, no change. Last thing I did was put the network back to the old linksys router and take the time capsule out of the equation. That was last night. Going to see if the network flakiness goes away. If so, the time capsule is being returned.
I am strongly suspecting the time capsule because I was there yesterday to witness a random disconnect of the printer. We were actually printing things, and then out of nowhere, the printer was seen as offline from all networked computers. At this time, when the printer wasn't seen on the network, I went to the airport utility, and the time capsule was not being found either. Power on, green light, computers airport utility could not see it. Strangely, all computers still had internet access and could access each other. Very strange. Once I was able to get the time capsule seen by the airport utility, printer functions returned.
Anyway, don't know if any of this applies to you. Just figured I would check.