Reason: This issue occurs because the new agent has the same NetBIOS name as a previously installed agent. When the agent is deleted from Operations Manager, the grooming of the deleted agent is hard coded to occur after two days. Therefore, the agent is not immediately groomed out of the database completely.
Solution: To work around this issue after the agent was deleted from the console, wait three days, and then add the new agent to Operations Manager. Or, make sure that two full days have passed, and then add the new agent to Operations Manager.