If the server having the error is running Active Directory, the fix is a bit more complicated for the same error. I had to manually remove entries from two locations:
1. Deleted the old Reverse lookups in the dns.
2. Used AD Users and Computers tool to delete the old dnsNode entries which somehow remained in AD (even when they have been deleted from the DNS) in AD: System, MicrosoftDNS, <domain name>.
The error in my case was caused by a router. It tried to register itself in DNS but its name contained a space. Being an invalid DNS character, it caused the error.
You might not have permission to access this file. User Action: Check the permissions on the specified file:
1. In Windows Explorer, go to the Systemroot\System32\Dns folder.
2. Right-click the specified database file, and then click Properties.
3. Click the Security tab, and then click Permissions.
4. Verify that you have the proper permissions to read, write, and run the file.