I've been receiving the "Transaction error-decryption error." for about a week while trying to send e-mail. RIM just poseted their Service Pack 1 for Desktop 4.0, I've downloaded it and installed it and it fixed my problem, it seems there was an error in their Desktop software for syncing the encryption keys.

http://www.blackberry.com/support/downloads/