We got an update from BlackBerry support on this issue this morning. Their senior development team discovered that the issue is with the signature algorithm that is used on the VeriSign root certificate.

The VeriSign root certificate (VeriSign Class 3 Public Primary CA – in our environment) uses MD2 with RSA encryption for the signature algorithm and MD2 is not supported in any BlackBerry OS at this time.

I think it would be safe to say that if any CA in your cert chain uses md2RSA as a signature algorithm, your authentication would be broken in the BlackBerry OS. (See attachment for sample certificate screenshot)

RIM has logged "bug" in their development tracking system, but so far has not committed a specific BB OS version for the fix.

We'll keep on top of this and keep you all posted.