You may have made it worse by changing those batteries! Was it a firewire communications error or host to host? If so the problem is in the network controller. That is the box that sits on the back of the machine. Its like a small linux computer. It could be a bad hard drive or corrupt software.
Sounds like a DHCP error, set the printer IP to static (Use the same one it was assigned by DHCP) and the issue should resolve itself.
I have xerox wc 7655 and one I think big problem. When I turn on machine after 5-10 minutes restart and then show communication failure, also I can't print anything.. I always must wait about 15-30 minutes to turn on again. Here is my software version 040.033.53210
Please help me.. No one from local services don't know what is a problem.. I changed CMOS battery, and some yellow timekeeeper battery on back of machine.