I've worked on tracking down the cause and solution for this problem for almost a month, and I have it at last! Microsoft support was profoundly helpful; my thanks to them.
The problem arose because the primary domain controller of my forest (it's a forest of two, but it's still a forest) was Windows 2000. This does not contain the well known security principles such as Network Service. Because I ran 'dcpromo' on a W2K3S system in a domain controlled by a W2K server, my W2K3S specific principles disappeared from view, but not from existence.
Apparently, if I had run 'adprep /domainprep' and/or 'adprep /forestprep' from my W2K3S CD on my W2K PDC before running dcpromo on my W2K3S box, I would have been OK. I'm not in a position to verify this. The fix which worked for me was to switch the PDC/RID/Infrastructure rolls to my W2K3S box, which I had intended to do some fine day, anyway. I understand that I could have switched right back to the W2K box afterwards and would have stayed fixed.
To switch roles:
- Open Active Directory Users and Computers.
- Right click on the top node and select "Connect to domain controller"
- Select the W2K3 DC
- Right click on the root node of the domain and select "Operations Masters..."
- On the RID, PDC & Infrastructure tabs, verify that Operations Master is the W2K machine, and the lower computer name is the W2K3S machine. Click "Change" for each.
- Verify that your ability to ACL a directory for Network Service suddenly and joyfully works!
- Switch the roles back if you like.
If this is beyond your privileges, see the other response I posed about using 'cacls' to work around the problem. This may be good enough; I just had to find out what was really going on.
There is a KB article related to this; http://support.microsoft.com/Default.aspx?id=827016
Also note that this solution assumes both machines are in the root domain of a forest. If you are in a non-root forest, the solution may differ and again, I'm not in a position to verify this.