Bizarre Network Printing
I install large (60ppm and higher) multi-function machines to networks and I just saw this on a Snow machine at a graphics house when trying to install a Creo print server ($40K+ for the Creo alone) there to a Konica Minolta C6501.
I had to remove all printers, go out and remove all of the PPDs for the devices, shutdown, go in as the administrator of the machine and reinstall the Creo as an LPR device, shared it and it worked. When I logged back in as the user the Creo showed up and was happy after I added all of the finishing options to it, fold, staple. binding, trimming et al.
I never, repeat never use the embedded drivers/ppd's. I jump to manufactures web site and grab the latest and greatest (also a problem sometimes) or the CD/DVD supplied with the device.
It's worth a try, my Creo was exhibiting the same issues after I installed the Creo the first time saying the server wasn't available, cannot connect to the server and the server is no longer a valid device on the network.