I've heard of this behaviour when the internal flash drive has problems and requires a replacment. On some devices this is removable and others it will require an RMA of the whole firewall.
Other things to confirm:
Have you confirmed that the new signing key is actually on the device?
The new and correct signing key for ScreenOS 6.3R21 begins with 308201ad as shown below.
The old key begins with 308201ac.
ssg5-serial-> exec pki test skey
exec pki test <skey>.
Flash base = 0x51000000, Flash end = 0x0, sector size= 0x4000
KEY1 N/A len =433
308201ad02010002818100fd7f53811d75122952df4a9c2eece4e7f611b7523cef4400c31e3f80b651magic1 = f7e9294b magic2=0
KEY2 N/A len =433
308201ad02010002818100fd7f53811d75122952df4a9c2eece4e7f611b7523cef4400c31e3f80b651magic1 = f7e9294b magic2=0
KEY3 N/A len =433
308201ad02010002818100fd7f53811d75122952df4a9c2eece4e7f611b7523cef4400c31e3f80b651magic1 = f7e9294b magic2=0
you could try the "B" version of the 6.3R20 code that removes the exploit to see if your device accepts this one.