I created an OU in AD and put my terminal server in it.
I then created a policy and selected the option to remove and disable the shut down command from the start menu.
On the terminal server from a command prompt, I ran gpupdate
No errors in the event log.
I did this about 3 hours ago and I still have the shutdown button on the start menu.