I solved the problem.
First, you have to revoke the certificate on Apple's Push Certificates Portal.
Second, in Server App go to Settings and click on "Edit" on the right of "Enable Push Notifications".
Third, click on "Change" on the right of Apple ID.
This is confusing because "Change" implies that one has to change the Apple ID. This is not the case.
Proceed and you will receive a new certificate from Apple.