Here’s the fix:
1. Delete the Trusted Key using ConsoleOne.
2. Use the Blackberry “Key Generator Application” to create a new one.
3. Go into the BB Server Configuration app on the Blackberry server and paste the new key into the “GroupWise Settings” tab.
4. Bounce the box, and all should be well.