1. Have you installed more than once onto this server?

Yes, but I totally rebuilt the machine from scratch afterwards.

2. Have you installed more than one instance?

No, I haven't..

3....

Yup...

I also just tried the following:

1)VNC'd into the problem SQL Server and succesfully registered another remote SQL server from there.

2)Tried to register the problem SQL server from the other...

there is a firewall, yes... but I have allowed traffic through port 1433 through it and I use it to remotely connect to another SQL server elsewhere.

The one that I...

Thanks for that, it is indeed listening on 1433 and I can ping it from my machine too.

Really weird this is, I've connected to lots of SQL Servers before and...

BTW, forgot to mention that I am trying to connect from a remote machine using TCP/IP