I actually just got this exact same problem fixed by a blackberry technician the other day...

He basically had me remove Desktop 4.0 and install Desktop 3.6 with the most recent service pack available. He told me that basically 4.0 is more directed toward BES users than Re-Direct users. Version 4.0 has a lot of extras in it that make the encrpytions go haywire for re-direct users.

After you complete your downgrade to version 3.6, go into your redirector settings and click the manually generate key option under security settings. He instructed me to manually generate the key, then hit apply. Repeat those steps 3 times (generating the key and then hitting apply).

That should take care of your problem.