Ever since the release of Exchange 2010 SP1, there have been numerous reports of users being prompted that they have to be redirected to another server, instead of the silent redirect that had worked like a charm until SP1. I blogged about this in September after I experienced the issue for myself. Since then, it's been one of the most-read pages on my blog.
I've just received word that the issue has finally been fixed in Exchange 2010 SP1 Rollup 2. This KB article describes the issue and the confirmation that it's been fixed by RU2.
You can get Rollup 2 here.