Pardon, porque eu não sou super experiente com várias distribuições Linux, mas pelo lado do Active Directory, isso soa como se você pudesse ter um problema com o seu RID Master. Se o pool estiver esgotado e não estiver sendo reabastecido, pode ser que os outros controladores de domínio não possam se comunicar com ele por algum motivo.
O que acontece sob o capô é o mestre RID aloca um conjunto de (i) 500 RIDs de cada vez para novos objetos, e quando isso chega a menos de metade de um novo pedido é feito e um novo bloco de RIDs é atribuído .
Eu recomendaria tentar um dcdiag completo e verificar se há algum erro (ou solicitar que seu administrador do AD faça isso) como uma medida inicial.