InfoPath Dev

As happens each year the certificate has expired on a couple of InfoPath templates and as I do each year I go back to the certificate server, generate a new one, install it.
Then I open InfoPath re-sign the form and re-publish it.
I go to the document library (SharePoint 2013) and try to open an existing document (XML) and get told the certificate has expired or been revoked.
So I go to advanced library settings and click edit the form (to ensure I'm dealing with the right one) and I see it is already signed with the new certificate.
So I go to library settings and select relink documents with this library and then click relink all.

Still can't open the existing templates - I get the same error.
This is happening in 2 separate form libraries that have been working for a long time.
Am I missing a step? 

You may just be struggling with a cached template. Open InfoPath Filler, and under New, find one of the forms that is giving you an issue. Right click and select either get update or remove, then try again.

 Seems that's exactly what it was - thanks very much!

Good deal. It is frustrating when that happens because you can't open the template to get it to prompt you for an update! One client I work with who has a full trust form has instructions for how to manually update the form (same instructions I gave you, pretty much, but with screenshots) on the home page of their SharePoint site to help users when they have issues.