Para qualquer outra pessoa que tenha esse problema, parece evidente que o XML GPO de layout do menu Iniciar não funciona com perfis obrigatórios.
Se você precisar alterar o layout do menu Iniciar no 2012 R2 (também acredito no Windows 8), exporte o menu Iniciar como BIN e importe de volta para o Servidor usando o powershell elevado.
Isso elimina a necessidade do GPO, pois substitui o arquivo do menu iniciar no perfil de usuário padrão, de modo que ele será aplicado a todos os usuários no logon.