The grace period is proportional to the complexity and time it would take to remedy the vulnerability. For example, take this thread on reporting a security vulnerability about a trusted certificate authority, a pretty serious problem with far-reaching consequences. One poster explains the reporting protocol well:
The rules of responsible disclosure, as decribed here, say that you should contact the vendor and negotiate a period of time - between 1 week and 6 months, depending on the depth of the changes required - in which they can implement a patch, revoke and re-issue certificates, publish security bulletins, etc, before you go public with your findings. The intention is that at the end of the negotiated period you get your public recognition, but your going public can't do any more harm - if the vendor has done their job properly.
I imagine, in your scenario, that the vulnerable vendor would (hopefully) relay the information to others. You could also contact CERT, who is trusted and has experience in dealing with such matters on a large scale. In a similar thread to the one I linked above, there's this:
You should let the developer(s) know privately so that they have a chance to fix it. After that, if and when you go public with the vulnerability, you should allow the developer enough time to fix the problem and whoever is exposed to it enough time to upgrade their systems. Personally, I would allow the developer to make the announcement in a security bulletin in most cases rather than announcing it myself.
We can probably agree that it would be a bad idea to go public immediately, because that would leave the door open for exploitation. So privately notifying them is the best way to go. In the meantime, they would probably fix it, upgrade, or switch to something else. What other reasonable options are there?
Finally, there are real-world cases of cryptographic vulnerabilities, and those algorithms were widely used. One example is Dual_EC_DRBG, an elliptic curve based algorithm, which was used for quite some time before being revoked due to security issues. I got schooled on it in this thread.