I believe your problem would be cause because of different serial numbers of the machines. Even thought you set up your keys the same way on both servers, when the key is built, it uses the serial number. Your key is stored in a a KeyStore area. This is what is used to decrypt. They would be different on each machine.
For anyone needing additional information IBM, while working with me, had me create the following data area with the following values:
CRTDTAARA DTAARA(QTEMP/QTADECRYPT) TYPE(*CHAR) LEN(62)
CHGDTAARA DTAARA(QTEMP/QTADECRYPT (1 10)) VALUE(‘TAPMLB01′)
CHGDTAARA DTAARA(QTEMP/QTADECRYPT (11 10)) VALUE(‘Q1AKEYFILE’)
CHGDTAARA DTAARA(QTEMP/QTADECRYPT (21 10)) VALUE(‘QUSRBRM’)
CHGDTAARA DTAARA(QTEMP/QTADECRYPT (31 32)) VALUE(‘KEYRECORD’)
As shown in this example the library is QTEMP but you can also create these in QUSRSYS permanently. When you perform a restore from one server to another with different serial numbers BRMS trys to create this data area. Also you must have media monitor turned off to do the restore. Lastly, of course, you need to have the Q1AKEYFILE and Key Stores setup the same as the source partition. All of these will allow for a successful restore.