Folder Redirection

First thing I would check is make sure you have the GPO setup in the correct OU.

I have created GPO before that apply to only Computers but created it in a Users OU.  With GPOs you have to make sure that you have it in the correct location so that it affects the objects.  Users\Computers.  Beyond that, it is hard to diagnose something like this without seeing it.  The other thing I would check is where is the GPO stored and can your PCs or Users access that location on the network.  If you put it in the Sysvol location like standard practice, you should be fine.  If you are not using the Sysvol, you have to make sure that the DCs are replicating correctly. Roger Stumbaugh