Letztendlich war dazu ein Neustart erforderlich. Nach einem Neustart ging ich zur obigen Bindung und schaute und es hatte das vorherige Zertifikat noch ausgewählt - nicht das im Screenshot. Ich habe das neue noch einmal ausgewählt und es hat funktioniert.
Es scheint also, dass IIS in diesem Fall verwirrt war und obwohl das GUI das neue Zertifikat als ausgewählt anzeigt, war dies nicht der Fall.