I recently installed Microsoft CRM Server in a lab environment. The install went smoothly.. every test passed successfully. But when I loaded up the Deployment Manager, I kept getting the error:
The specified Microsoft CRM Server is not responding. This might happen if it is currently unavailable or is not a Microsoft CRM server. For more information contact your system administrator.
Uninstalling/reinstalling didn't help. I researched a little and found that perhaps MSCRM didn't like the fact that I didn't add the server alias "mscrm" to DNS. I also saw that some people were able to log in to MSCRM from any computer other than the server itself. I decided to add a CNAME alias to the DNS that points to my computer's name and try to login from a different server. It was then that I noticed I couldn't reach my CRM server at all. I checked and sure enough, even though network settings didn't a lock, my firewall was on. I would imagine that since I tried logging in locally that a firewall wouldn't care but apparently it did. I turned off the built-in Windows firewall and was instantly able to login to the CRM server.
Google shows that many people have this problem, hopefully, this post may help you or someone you know 
And now to go and play with this good-lookin CRM software...