You can "regenerate" the certificate on your gateway, but it will work only if you take care to reuse the same name and key.
This is a certificate chain: the certificate on the gateway is the "CA certificate" and the clients have been issued certificates by that CA. Such a client certificate will be deemed valid (aka "acceptable") if whoever does the verification can build a valid chain. Conditions are listed here (don't go read that, it will destroy your sanity); they mostly boil down to:
subjectDN of the issuer must match the
issuerDN of the issued certificate.
- The current date must lie between the
notAfter date of each certificate.
- The signature on the issued certificate must be successfully verified with regards to the public key in the issuer certificate.
The consequence is that if you produce a new CA certificate (for your "gateway") with a longer validity range, and take care to use the exact same name and the exact same public key, then the new certificate will work as a replacement for the old one.
A further complication is that whoever will have to validate the client certificate will need to access the new CA certificate instead of the old one. Possibly, the client may send it along as part of the protocol (this happens in some protocols, e.g. SSL: when the client sends its certificate, it actually sends a complete chain), but this will require client systems to know it. Any certificate may contain a link (URL) to a place from which the issuing CA certificate may be downloaded (it is called Authority Information Access); if that is the case, then you will want to put your new CA certificate at that exact place, replacing the old one.
Summary: your "Plan B" may work, but only if you reuse the same name and key in the new certificate, and it may depend on the exact usage scenario. Your CA software may be troublesome if it insists on generating a new key pair.
Note: some CA avoid this situation by enforcing nesting of validity dates: if a CA's certificate ends on December 13th, 2014, then it will refuse to issue certificates with a
notAfter date beyond December 13th, 2014. Microsoft's CA (Active Directory Certificate Services) is of that kind. I take it that your CA software does not apply that rule.