I posted a thread/FAQ on this problem in this forum just a few days ago:
http://www.blackberryforums.com/view...ht=transaction
Basically you have these options:
* Re-send service books
* Recreate your encryption keys for the redirector/BES
* Get and use dbclean.exe on your computer as somewhere the old encrption key is still being used..
see above link for more information!