In the Certificate creation window have you tried entering you IC username and IC voicemail password (
not your Windows login)?
If the phone was working before updates, I am hoping it would still be configured properly on the back end, and the IC login should allow the certificate creation.