Hm. The original problem definitely sounded exactly like yours. However following the links to the recommended solution, I don't see how tramp is related. Anyway this looks way more complex; I certainly have never needed to copy a file like ~/.emacs.d/server/server to my local host. Things Just Work, with no extra help. If xterm works then it's probably not an issues with Xauthority etc. It seems bizarre to me but I suppose it could be a hostname thing. If on the server you say "ping server" does it work and give you a real IP address (not 127.0.0.1)? If on your client you say "ping server" does that work and give back the same IP address?
Have you tried starting Emacs in --daemon mode rather than using start-server? What version of Emacs do you have?