Once thing you might want to try, depending on where you applied the GPO, is create a new Group and move the users into it. That might resolved the issues if the GPO was placed the OU level. If the GPO was placed at the Domain level (not recommended in my opinion), then you may need to change the policy to Disabled, then run:
secedit /refreshpolicy machine_policy /enforce
From the server. This will enforce any policy changes immediately instead of waiting the 15 minutes for the changes to replicate. As for the run command issue, this could also be restricted be an errant GPO setting. Check under GPO->User Configuration->Administrative Templates for any settings relating to the missing RUN command for your users. In that situation creating a new OU with a blank Group Policy might rectify the problem.
Hope that helps!
Ariston Collander
ariston@coxcomputer.com