I have a HP Color LaserJet CM6040 connected on a network, and have many hosts (laptops) connected wirelessly to it, but some of the hosts can't print on this printer. I've restarted the printer and re-installed de printer on this hosts but the problem continues and i'm out of ideas.
Check that all the other devices are using the right drivers and the same version? Also leave the printer queue window opened. See if it goes into the queue and disappear after you press print.