I picked up a fairly cheap Lexmark X4550 wireless printer/scanner/copier about 6 months ago and soon noticed that it stopped working every time I restarted the router.
After a long conversation with a fairly patient technical support guy at Lexmark proved mostly fruitless, I dug a little further and ran a packet sniffer (Wireshark) over an attempted print job.
This prompted me to double-check the printer settings, which showed a device URI of lexnet3://192.168.1.3:1. Which is certainly wrong, as the printer is at 192.168.1.4. I'm not sure why it doesn't just use DNS properly, but anyway.
Trying to correct this, I stumbled across this post explaining how to modify the device URI via the CUPS web interface available on OS X. And it works! Good old Unix!