Thanks for the reply.
I just solved the issue myself :).
This is what i had to do:
1. Start>Run> DCPROMO /FORCEREMOVAL, run this wizard in order to remove AD from the dodgy server.
2. Go through AD Users and Computers and AD Sites and Services. Deleted any references and any NTDS connections on the dodgy server. Then Delete the Server from AD Sites and Services.
3. Delete Server from the Domain Controllers OU in AD Users and Computers.
4. Run the ntdsutil and run a metadata clean up as per:
http://support.microsoft.com/?kbid=216498
5. Do into DNS Management Console, go into the _msdcs.domainname under forward lookup zones, deleted the reference to the dodgy AD server.
6. Right-Click the domain (test.doman.com for example), go to the name servers tab. Select the Dodgy server and click Remove, Click Apply, then click OK.
7. You can now go back onto the dodgy server and then reconnect to the updated domain.
8. If you need to, you can now run dcpromo and re-add to Domain as a domain controller.