Unexpected "Certificate Error" on N96 -- typical fixes did not work

[kludgey]

When attempting to install my application on a Nokia N96, i get "Certificate Error. Contact the application supplier."

My application is signed using a valid open signed developer certificate.

I have verified the typical causes of this error are not my problem. In the phone's application manager options, I have verified that "Online Certificate Check" is set to "Off" and "Software Installation" is set to "All". I have also verified that the date set on the phone is correct and falls within the range specified by the certificate. Finally, I have verified that the correct IMEI is included in the certificate.

The device is a Telefonica (Movistar, Spain) branded N96 using firmware version 12.043

I have successfully installed my application on an unlocked N96 using firmware version 11.018. I have also successfully installed on Telefonica branded N95 devices.

Is there a known issue regarding either Telefonica branded N96 devices or firmware 12.043 and developer signed applications?

Any help is greatly appreciated.
Thanks.

[ltomuta]

There's one more thing I can think that you should verify, the security certificates installed on the phone. Under Tools -> Settings -> Security -> Certificate management -> Authority certificates see if you have the four Symbian (A to D) root certificates.