Check the ports that SQL Server is using? Are you using the default ports? After you determine what port SQL Server is Listening on then you can attempt to register the server using that port. If you still can not register the server then try to telnet to that server on the SQL Server port and if that fails you may have a firewall issue and you will need to get with your networking team. If you need more help let me know
This page has a list of things to look at which will help you troubleshoot your remote connection issue.
Also have a look at the output of master..sp_configure with no parameters which will displays all configuration options and check for remote access which has to be 1 (by default)