I'm having the same issue, but only on one particular computer model.
The only difference between this one (Lenovo X61 Tablet) and every other pc we're using is that we had to use the factory configuration for the tablet. We couldn't get the hardware to work after reinstalling XP w/SP2 from scratch, so we needed the factory defaults. They even have it setup by default to override your home page with theirs (boo!), but we've gotten around their branding by using their app Access Connections to override their first override. Get it?
I absolutely cannot put my finger on it, but I'm assuming that's due to lack of knowledge on any local processes that manage folder redirection.
What can I check on the local pc that might indicate why folder redirection is being blocked? Share permissions are set just fine (works perfectly from any other computer on the domain with any username) and the "gpresult /v" says that all aspects of the policy are being applied EXCEPT the folder redirection!