Umm.. Did you try the steps I wrote above ..? You'll need to restart the system for changes to be in effect. The restriction comes in effect as soon as you apply the policy but removing admins from this restriction comes in effect when you reboot the PC.
And there may be another case, .. Do this :
Start > Run > lusrmgr.msc {Press Enter}
Under the Users section, double click on the User that you want not to restrict.
See if he's listed under "Users" group. If the entry is there, remove it.
See the screeny: