(Edit 24/02/15 - corrected registry location)
Lenovo were preinstalling a Start Menu replacement on Windows 8 called Pokki. Uninstalling this works for a single user, but as soon as another user logs in, the application is reinstalled. This is not listed as Metro application that can be uninstalled using remove-appxpackage or remove-appxprovisionedpackage, as listed here (new window).
To uninstall this for all future users (This will not delete it for any users that have already created profiles, they will need to be done individually – see the end for more details):
Go into Programs and Features, and uninstall it like any other application
Yes choose to uninstall
Go into the \users\public folder, and delete the pokki folder
You will need to show hidden files and folders (see here for instructions - new window), and go in to the \users\default\appdata\local folder, and delete the pokki folder
Open regedit as ad administrator, select HKEY_USERS, click the file menu and select Load Hive…
Navigate to \users\default and select NTUSER.DAT
Give the hive a name, eg: pokkiDefault and click OK
Navigate to HKEY_USERS\pokkiDefault\Software\
Delete the POKKI key
Navigate to HKEY_USERS\pokkiDefault\Software\Microsoft\Windows\CurrentVersion\Run
Delete the Pokki string value
Select the HKEY_USERS\pokkiDefault key, select the file menu, and Unload hive… and select yes.
This will not delete pokki from profiles that are already created. You can however delete the pokki files from each user profile, and use the regedit method above to load the other users hive and remove it from their startup. I haven’t tried it but would also look at removing it from their Programs and Features list via this method: http://support.microsoft.com/kb/247501 and also looking in their hive at the equivalent HKCU registry location.