O problema era que um token estava sendo enviado e a negociação tentada automaticamente quando dentro da rede AD, mas sempre falhava devido à criptografia usada ao gerar o keytab.
Originalmente usamos -crypto DES-CBC-CRC mas assim que mudamos para o -crypto RC4-HMAC-NT o problema desapareceu.