Yes, if they are the same model all you should have to do is replace the MAC and reset as you did.
If the 7821 has been previously registered to another CUCM cluster, it is possible the ITL (initial trust list) needs to be removed. Go through the Settings Menu and reset the Security settings. (Or do a factory reset.)
If the 7821s were purchased, double-check that the phones are Enterprise phones and not 3PCC phones. (3PCC = Third-Party Call Control). Read the label on the back of the phone. If the label has “3PCC” or “3PC” or “3PW” after the model number, then it is an MPP/3PCC phone. Otherwise it is an enterprise phone.
Let us know what you find. If neither situation applies to you, we can look at the log files in the phone to see if we can figure out the problem.
Maren