I don’t remember how we debugged it at the time, but I’ve run into very similar symptoms that were caused by clock skew between client & servers. Increasing the validity window to both past & future by a longer period helped resolve it.