Have you tried allowing auto registration? There is probably some parameter configured incorrectly. If you don't want to turn on auto registration, you can collect a packet capture from the phone and CCM traces to see what is going on.
Phone Packet Capture:
https://supportforums.cisco.com/docs/DOC-11735
CCM Traces:
http://www.cisco.com/en/US/products/sw/voicesw/ps556/products_tech_note09186a0080094e89.shtml
There is also the off chance that it is a bad phone, try swapping in another phone of the same model and firmware version in the same switch port, if that one works fine and the broken phone stays broken on a 'known good' switchport, then open a TAC Service Request to see if the phone needs an RMA.