I'm not sure what you've tried to do before, but here's what I just did and had success:
1) Downloaded the Tomcat 5.5.27 Windows Service installer and installed it.
2) Dumped the TomCat5 service security descriptor using "sc sdshow tomcat5", which showed me:
D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWLOCRRC;;;AU)(A;;CCLCSWRPWPDTLOCRRC;;;PU)
This is a pretty common security descriptor for services. I've seen it verbatim on some Microsoft services. The SYSTEM and built-in Administrators have "full control", "Power Users" can stop, start, and pause the service, and "Authenticated Users" can query properties of the service (I'm glossing over a bit here).
3) I created a limited user called "bob" on my box, opened a "RUNAS" command-prompt as him, and got his SID from "WHOAMI /ALL" (a command that's on Windows Server 2003 but not on XP... don't know about Vista and Windows 7 off the top of my head). I verified that Bob could not stop / start the Tomcat service (using "NET STOP tomcat5"). I received the same error you report in your post.
4) From my regular administrator command-prompt, ran the following:
sc sdset tomcat5 D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWLOCRRC;;;AU)(A;;CCLCSWRPWPDTLOCRRC;;;PU)(A;;RPWPDT;;;S-1-5-21-1409082233-484763869-854245398-1009)
This SDDL string gives Bob's SID (S-1-5-21-1409082233-484763869-854245398-1009) rights to stop, start, and pause the service (RP, WP, and DT, respectively).
5) I flipped back to my "Bob" command prompt and verified that I could now stop and start the service using NET STOP and NET START.
I'd recommend creating a group to delegte this right to, putting a user in that group, getting the group's SID (using WHOAMI or any other tool) and modifying the security descriptor this way.
I would think that using Group Policy to modify the security descriptor would work fine. I have seen cases where some services don't like the default permission that a group policy-based modification puts on a service (look at this posting about the Windows Search service if you want to see what I'm talking about: http://peeved.org/blog/2007/12/07), but that has been uncommon in my experience.
If you want more background on security descriptors for services, have a look at http://msmvps.com/blogs/alunj/archive/2006/02/13/83472.aspx and http://support.microsoft.com/kb/914392.
whoami /priv shows the current STATE of the privilege, not the actual privilege. You'll see the same thing using the "administrator" of the domain's account. It gets "enabled' when you actually do it.
A good explanation is here: http://alt.pluralsight.com/wiki/default.aspx/Keith.GuideBook/WhatIsAPrivilege.html
Quote from there:
The normal pattern of usage for a privilege can be demonstrated by an example. Say you want to reboot the system. You know that this is a privileged operation, so you reach up into your process token and try to enable SeShutdownPrivilege. If you've been granted this privilege by policy, your token should have it, and so you'll be permitted to enable it. If you haven’t been granted this privilege, your attempt to enable it will fail, at which point you'll need to deal with the fact that you're not allowed to reboot the system (in a desktop app, you could inform the user of her lack of privilege with a message box, for example). Assuming you've succeeded in enabling the privilege, you'll call the Win32 function ExitWindowsEx to request a reboot. Finally, you should disable the privilege. Notice the pattern here: enable, use, disable—just like the policeman with his lightbar.
Because you're rebooting the system, you might argue that disabling the privilege is a waste of time. But just as you should never get lazy and allocate memory without freeing it, you should never enable a privilege without disabling it as soon as you're done using it. You never know who will cut and paste your code in another project! Besides, how does the routine know that the reboot will actually happen and that your program will actually exit? Often users initiate a reboot only to cancel it when they realize they need to save some work first. It's tough to know all these things deep down in a routine that's responsible for actually implementing the reboot. Make sure each of your security primitives (like privilege usage) follows best practices. Don't take shortcuts.
Some privileges are meant to be enabled all the time if they’re granted. SeChangeNotifyPrivilege (also known as "Bypass Traverse Checking"3) and SeImpersonatePrivilege are notable examples. These are like the policeman's handgun — he’s granted the right to carry it on the street, and he's never on the job without it. If you're granted any of these privileges by policy, the operating system will enable them by default in that first token you get at login time, so you shouldn't need to worry about messing with them at runtime. Many Win32 functions (but not all) incorporate the enabling and disabling of privileges as a convenience. Furthermore, I expect that, as the .NET Framework continues to abstract more of the Win32 API, you'll have less and less need to worry about enabling privileges manually. But this is a technical detail. Security policy will still control who can and cannot perform privileged operations, so you should be aware of the privileges defined by Windows so that you know what requirements your programs will have with respect to security policy.
Best Answer
For posterity... I have no idea what I was doing wrong before, but I revisited this and was able to get it to work twice (a second time just to make sure I wasn't crazy) using the exact process I described above with a group policy object.
The only thing I can think of that I might have done differently was giving the Backup user Read privileges as well as Start/Stop/Restart privileges on the services.
Thanks to those who helped.