Let a be an integer with |a| > 1. Let f(T) ∈ Q[T] be a nonconstant, integer-valued polynomial with positive leading term, and suppose that there are infinitely many primes p for which f does not possess a root modulo p. Under these hypotheses, Ballot and Luca showed that almost all primes p do not divide any number of the form a^f(n)-1. More precisely, assuming the Generalized Riemann Hypothesis (GRH), their argument gives that the number of primes p≦ x which do divide numbers of the form a^f(n)-1 is at most (as x→∞) π(x)/(loglog(x))^r_f+o(1), where r_f is the density of primes p for which the congruence f(n)≡ 0 (mod p) is insoluble. Under GRH, we improve this upper bound to << x(log(x))^-1-r_f, which we believe is the correct order of magnitude.