Tivemos um problema semelhante em que as estações de trabalho demoravam cerca de 10 minutos para efetuar login. No entanto, se o cabo de rede fosse desconectado e o computador reinicializado, eles se conectariam imediatamente.
Descobrimos que os logons lentos foram causados por um driver de impressora que estava sendo instalado, mas que exigia a entrada do usuário, o que obviamente não poderia ser fornecido porque o usuário ainda não estava conectado.
Tente ativar a tela de boas-vindas do Verbose no GPO. Isso pode mostrar onde o PC está ficando preso.