terminal server users seeing administrative tools.

The admin tools showing up in the start menu are nothing but menu items under c:\Documents and Settings\All Users\Start Menu\Administrative Tools.

Your users are likely seeing those from the above location. A couple of things you can do:
1- Control what start menu items show up, either by manually moving items from the All Users start menu directory.
2- Control what shows up with GPO. (I don't believe Administrative Tools is one of the ones that can be controlled via GPO.
3- if your users have domain user privileges on the domain, they would not be able to use administrative tools to do anything harmful on the domain.
4- If you users have user privileges on the local terminal server, they will also not be able to use these admin tools to do anything harmful there either.

So bottom line, you have to look at two things:
What access your users have, and what they can see. To achieve this, you need to control the start menu itself, and what access they through the tools that are in the start menu.

If you have any specific questions about this, let me know, and I'll try to clarify

Remove the everyone and domain users group from the security tab in
C:\Documents and settings\all users\start menu\programs

Ensure that administrators group has full access

Looks like everyone . Power users and users have read&execute.

I wouldn't do the security change that madhurjya123 suggested. All users affects all users, and will actually remove access to users to every single menu item in program files. If anything, to stay with that previous suggestion, you can move the Administrative Tools piece out of the "Programs" folder, and put it outside of the start menu folder, and change its NTFS perms to  not allow access. Later, you can always add that folder to the actual user start menu to whom you want to give access to these items.

OR

you can potentially go with madhurjya123's suggestion, provided that you have setup the "Default User" account with all the appropriate start menu items. In this case , you can probably remove access to all users from the all users. it's not quite best practice that way, but it'll accomplish what you're trying to do.
for this to work, by the way, you need to start with clean profiles on the server, otherwise, the "Default User" profile will have no effect on users logging in.

Correction: You need to remove domain users and everyone from :
C:\Documents and settings\all users\start menu\program\Administrative Tools

*Programs