I'm not 100% sure about this, but here goes - this is based on a recent call I made to tech support regarding a slightly different issue:
First - be infront of the base station holding the new phone in your hand. Have the new phone switched on.
Hold down the Page button on the base station until it beeps twice.
After you hear the two beeps, press the page button 7 times. The little green light will flash.
Hold down the Page button on the base station again until it beeps twice.
Grab the phone you are setting up, and hold down the program button until you see P1- on the screen
when you see P1- let go of the program button and enter 0000, then press and release the program button on the phone.
In a few moments, if that has worked, you should see the phone come online.
If that doesn't work, and you're in Australia, talk to the TecHelp line on 1300 369 193. They are only open during business hours.
Hope it helps someone.
Michael Phipps, December 2007