We ran into this when we migrated. Open your GPO that you're using with gpmc.msc - or the local policy editor via gpedit.msc. Navigate to User Configuration > Policies > Administrative Templates > Control Panel > Personalization Look for the setting named 'Prevent changing theme' and make sure it is disabled or not configured. This will no longer prevent users from changing the themes, but they WILL be required to manually change to another theme (such as Aero). You might want to make sure that User Group Policy loopback processing mode is turned on so the settings will apply to the machines versus the users - depending upon where the GPO is applied. (Computer Settings>Administrative settings>System>Group Policy) I hope this helps.
