Renaming Domain Controller Went Weird… Help

I have a small network with a single domain controller, running Windows Server 2008 R2. All was going well until just now.

I had previously had a Windows Server 2003 DC. I demoted it to a workstation and promoted the new 2008 R2 to a DC successfully and used it like that for a couple weeks.

However, to completely migrate everything to the new server it had to get the name of the old server – 'SERVER'. I followed the instructions on http://www.petri.co.il/rename-windows-server-2008-domain-controllers.htm but after step two it told me "Active Directory Domain Services already contain a Computer Account or a Server Object with the specified name: SERVER (blah blah, remove them, account already exists)".

In my infinite wisdom, I decided to reboot the 2008 R2 box. Now I am getting all sorts of errors about not being able to contact the domain security controller. I've also noted that in adsiedit.msc that it lists the server in OU=Domain Controllers as "CN=OLDNAME".

I'm not really sure where to go from here. Unfortunately, I didn't expect this to blow up on me so I don't have a backup to just swap back to.

Edit:

Renaming the new server back to the original name with netdom said that it had failed because it couldn't contact the domain, but it had actually succeeded – the System control panel where it lists the computer name contained the message about needing to restart to get the new computer name. After a reboot, it is now working again (hooray, at least I'm not worse off than before).

I took a poke around in Active Directory Sites & Services and it seems the old server is still listed as an object. (It was not listed under Users & Computers with its old name). I'm going to delete it since there is currently no computer on the network with that name and re-try the renaming tutorial I linked from above.