Well, thats was todays challange and using lots of handy hints from some other site, It took a while, but it boils down to first controlling the start menu itself. Using group policy I redirected the start menu for the users logging into the terminal server, Once I had this redirection I could control the ‘All Apps’ window. This was setup as per requirements and then I setup the application pins as required. Using powershell you can then run the Export-StartLayout -Path c:\Temp\StartLayout.xml -as xml command to get the Layout Information and we can again use group policy to setup that layout for all users.
And bingo, we can now control the start Menus of all the users on a Remote Desktop Services Server.