Network Configuration Operator

Have you tried running GPUPDATE /Force on the XP clients?
Another Membership might be actively Excluding them or over writing it?

Are you working on a domain? If so, the above two should solve it.

If you are not on a domain, you'll need to add them to the group on the local account on the computer, not the 'domain' account on the server.

Remove the GPOs, restart the PC, force update, then try changing it. Leave them in the Network Op. category to see if the GPO is causing it or if its a security issue somewhere.

They are logging into the domain and not a locally configured account, correct? If they are not logging into the domain, the security will be based off the local account, which by default in XP might limit their Network abilities.

Also in your GPO, you can change the settings per user and per computer and there is a section for local rights that you should review.

I would really pull the GPO to see if that is causing the problem. If it is you may want to recreate your GPOs but add more. More GPOs stacked and each one only working on certain areas like "Desktop lock down," "Security Updates," User configuration" and "Computer configuration."
Doing this you can pull select areas of your GPO configuration from everyone instead of having it all sit in one GPO and require constant modification.

Open up Active Directory Users and Computers. On the OU (Users, Computers, etc. They're like Folders) Right click on it and Select Properties (I think off hand) then move over to the Group Policy Tab.

Don't DELETE anything. You "remove" the link by selecting to remove it, which basically breaks the link from the OU to the GPO. If you delete it, you can't get it back easily and it may cause further problems if something doesn't remove properly.

You'll see the option to Edit the GPO as well. Unfortunately, the base GPO editor that comes with Microsoft doesn't really do a great job in showing you what has been changed. Thus, I would recommend to Edit it and look through it to see if anything has been set. You can tell this because it'll say on the right side a setting. Many will say something like Not Configured or something to that effect. Others may list something different.

There is a generic GPO that is always applied as a standard. I would remove the one, or additional if present GPOs. Create a new GPO based on the Default GPO and look through it. You'll see where you can edit for the User and for the Computer. My advice on editing is to always edit for the User and not the Computer. If you set something for the computer, even an Admin won't get access to it.

Don't get overwhelmed by the GPO. It basically is everything you can configure on a Windows XP computer in a list by category. You can lock down allowing someone to change the Desktop Background to changing the Default password security to be 50 characters if you want.

Again, my advice would be if you change something "security" wise, I'd create a new GPO called Security, make your changes in that and apply it. Then go about making a new GPO for "settings" or "desktop settings" for that. Should something come up, you can quickly 'remove' the GPO link and people will get access again. It makes for a lot easier troubleshooting.