Could it be that the jump is to high?? Going from 2.13 to 2.16? We have upgraded from 2.14 to 2.15 and from 2.15 to 2.16 and didn't need to do anything with the certificates.
Could be that. Though you'd think that kind of things is not subject to changes across versions..
At least it's documented (if it wasn't already)