With what key mode are the keys created? Depending on the key mode, you might just be able to synchronize the keys with the server to get the signature renewed. You can manually force the Organization key to renew signatures of all keys on the server by starting an SSH session and issuing the following command:
pgpkeymaint --update-sigs
More info on setting up SSH here if you need it:
https://support.symantec.com/en_US/article.TECH171773.html
Since it is just an expired signature, you should be able to get that signature renewed, and not have to generate a new keypair.