I had a similar issue:
I bought a copy of OEM XP Home.
1. Ran it for 2 years on my 1300 AMD TB- PC133
2. Decided it was time for an upgrade for gaming (CPU, RAM, MB, PSU).
3. Went to reinstall XP and activate it, I couldn't activate it.
4. Called M$ and told them that I bought this OS but upgraded my hardware.
5. They asked me if it was installed on any other PC and I assured them that it wasn't.
6. M$ proceeded to give another type of COA that consisted of only numbers and now everything is fine.
A phone call that lasted for only less than 5 minutes and all is well. HTH
Edit: BTW they did check my current COA to see if it was one of the ones that was pirated! Beware if it is a pirated copy!