We have had a run on this one lately and the fun part is, every one of them was a different fix. Here are the fixes listed below.

1. manually generated a key 3 times.
2. Put the sim card in a 7100 and generated key 3 times, then put it back in the 7230.
3. deleted and re-added the user in the BES server.
4. Deleted the address books. (do a back up first. In fact do one before any fix)

Upgrading to 4.0 did not help any of them.

I am hoping 1 of the 4 will fix my future issues with this problem. Hope this helps at least one person from sitting on the phone with RIM tech support for over 7 straight hours.