What would cause a certificate installed on iOS to be invalid?

I recently installed two certificates (for use in signing mail) on several iOS devices. Both certificates derive from the same trust chain and were purchased from the same vendor on the same day. The only difference between them is that they are associated with different e-mail addresses. Both work fine on OS X in Mac Mail. But when they are installed on iOS devices (using iPhone Configuration Utility after exporting to .p12 files from Keychain Access) one works fine while the other is flagged as "not trusted". What could account for this difference? --- Update: 5.1 does not fix this.