Added computer to domain, doesn't show up in Active Directory

I recently had a computer crash.  So I reloaded it, named it the same thing and added it to the Domain.
I made sure to delete the previous entry before joining the domain.
The computer asked for domain credentials, and successfully added itself.
So I rebooted and I was able to log in with domain accounts.

However....

There's always a however...

The computer didn't show up in Active Directory Computers.
It didn't show up anywhere in AD.

I went back to the computer, removed it from the domain and added again.
Standard procedure.  Says welcome to the domain and requires a restart.  I oblige.

Check AD, still not there...

I thought I'd change the name, didn't work because the computer account wasn't found...

So here is how I got it to work:
Removed the computer from the domain.
Reboot.
Renamed computer.
Reboot.
Joined domain.
Reboot.
Verified account in AD.
Changed name on computer.
Reboot.
Verified account in AD, it was now the name I wanted to use.

All done.

Stupid PITA.