How is the print server connected to the router, wired or wireless?
What wireless modes are you running? Mixed? Single? Try Single mode G to test.
What security mode does the print server support? WPA or WPA2?
Setup Reserved (Static) IP addresses on the router for your devices.
Ensure DNS IP addresses are being filled in under Setup/Internet/Manual.
Ensure Advanced DNS Service is disabled if you have this option.
Ensure DNS Relay is enabled.