I have been trying to add new SIP phones, 7841s and SPA504G, note, I have added a few in just recent past, it's a Network of roughly 500 cisco/3rd party phones & 4 TPs. We use Cisco IP Phone 7942 too.
On the CUCM System version: 10.5.2.12901-1, it immediately rejects the new phones, on these new 7841s, phone gets correct IPs of LAN, TFTPs etc, keeps writing "registering" on the screen for DAYS!...On the SPA504G, It gets the IPs, but the directory number doesnt show on the screen, I have done RESET multiple times on both.
To add to Johnathan's great points -
Check the default firmware version on your CUCM. We've seen some of our clusters not keep up with the recommended updates. So when brand new phones arrive they come with a much newer version and then have to downgrade. This does not always work. Checking on the firmware download / update status will confirm this.