Hi,
I had this same problem 'till I carefully followed the exact instructions. The pin probably has not been chaged (who bothers?). Follow the instructions up to the point were it says the phone screen says 'registering...' and then press and hold down the 'find phone' key on the answer machine. After a few seconds the new handset should register.
Tony b, January 2011