Can you clients resolve correctly the new server hostname?
When you changed your OS X Server name (never a good thing to do BTW) did you check DNS records were still OK on the server? Did you run 'changeip' command on the server?
If you didn't run 'changeip' have a look at the command — 'man changeip'.
Yes the other clients can still backup to the OS X sever
The MBA was restored from a time machine of an MBP. That MBP could still backup to the server. I deleted that backup but the MBA could not backup to it. Actually it will connect TM asks for login credentials, it would even see the free space available and start counting down. As soon it hits 0, it will say backup disk not available. What's funny though is I can still access shares and even do screen sharing with the server.