The fix for me was to install the latest minidriver (not sure if this is what actually helped), but more importantly, reboot afterwards, and then the latest certificate showed up in certmgr.msc under personal/certificates.

So it looks like the cert was not there initially, and it was trying to use the new yubikey with the old cert file.

Also if it asks you to sign twice every time you sign, it's likely because you have the old and new certificate in there, so just remove the old cert from certmgr.msc and then it will only ask you for your pin for the current certificate.