Before I could name the new server, the old server needed to be removed from Active Directory. I went into Active Directory, found the server in the appropriate folder, right clicked it and selected Delete. After clicking Delete I recieved the following error:
The object
After clicking OK I recieved an error message stating Access Denied.
To correct the problem from the command prompt I opened ADSIEDIT.msc on the Domain Controller. In ADSI Edit I browsed to the correct container folder and expanded the server I was trying to delete. Once expanded, I was able to see a folder under the computer name. I right clicked on the folder and deleted it. Once deleted I was able to delete the server.
I verified the server was removed from DNS and was able to successfully name my new server the same name as the one it replaced.