Clients wouldn't know that there's two certificates for the same domain issued by two different CA's and throw a warning flag?
They would just see whichever certificate is currently 'active' on the server and as long as it's valid, it should be used?
CAs do not typically publicize their clients and certificates, or share notes. You could get a thousand certificates from a hundred different CAs, and switch between them every five minutes, if you want.
(The Certificate Transparency project to create public, auditable logs of certificate issuance is changing this, but few CAs participate yet, and CT doesn't restrict issuance, only document it.)
It's common for large websites to have multiple valid certificates. They may use different certificates in different data centers, or be in the middle of a careful transition, as you are. For example, www.google.com issues new certificates weekly, each of them valid for several months; or see the earlier Stack Exchange questions Why does Facebook serve several SSL certificates? and Why does Google SSL cert change so frequently?.
There are two issues you may encounter. My last link demonstrates the first one: The question was asked by someone using the Firefox extension Certificate Patrol, which does alert users when websites replace their certificates. But it's not widely used, and its users should be familiar with the headaches it causes.
Second, the HTTP Public Key Pinning (HPKP) standard changes everything. If you set it up, it can prevent modern clients from accepting new CAs or certificates for your hosts. To make changes, you would have to update your HPKP configuration and wait until the old one has expired on all clients, or suffer the consequences.
Finally, i think it's unusual that your CA is preventing you from buying another certificate — there is no technical reason for it, and they are turning down money — but that's on them. Maybe you can use their "buy a new certificate" interface instead of their "renew your current certificate" one?
In the future, your new CA may not restrict you like this.