Error: The Address Book does not contain a cross certificate capable of validating the public key.

If you can see in your log file the following error:

This is normally caused by the id used for promotion not have a cross certificate in the local names.nsf.

To fix this you will need to switch to that promoting id file in your local Notes client and access anything and then accept the cross certificate message that will appear.
Then you can switch back to you ordinary notes.id file and the promotion should run through and get past this error.

If you don't have access to the id file used for promotion, then ask one of the administrators to do this for you in your Notes client.