A small learning rate should reduce the probability of overflows in the gradients, which could create NaNs. However, if the scale factor is still too high, even a low learning rate might cause it.
Could you check, if the scale factor was reduced in the first iteration(s)?