I was able to solve this - I suspected that the service used by the app service certificate renewal didn't have permissions to update the key vault secret and turns out I was correct.
To solve the issue, I had to grant secret list, read and write permissions to Microsoft.Azure.CertificateRegistration (principle id f3c21649-0979-4721-ac85-b0216b2cf413). Once I did that, when I rekeyed the certificate, the secret value was updated with the new cert and the manual sync resolved the linked app service private certificates.