I had an issue today with a phone that wouldn't talk to our BES so I talked to Nextel's Blackberry Tier 2 support and it turned out that when the phone was ordered, a feature designed for another model of Nextel Phone was enabled that was causing the blackberry not to see anything.

I think I saw a decryption error before and it was because a new key needed to be generated but in your case it may not be.

Try going to c:\Documents and settings\yourusername\Application Data and renaming the Research in Motion folder.

(I usually call it something like Research in Lotion, or Crackberry in Motion) and restart your desktop manager and resetup the phone's profile.