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.
Disclaimer: As with everything else at Cool Solutions, this content is definitely not supported by Novell (so don't even think of calling Support if you try something and it blows up).
It was contributed by a community member and is published "as is." It seems to have worked for at least one person, and might work for you. But please be sure to test, test, test before you do anything drastic with it.