Quasireal photons exchanged in relativistic heavy ion interactions are powerful probes of the gluonic structure of nuclei. The coherent J/psi photoproduction cross section in ultraperipheral lead-lead collisions is measured as a function of photon-nucleus center-of-mass energies per nucleon (W-gamma N(Pb)) over a wide range of 40 < W-gamma N(Pb) < 400 GeV. Results are obtained using data at the nucleon-nucleon center-of-mass energy of 5.02 TeV collected by the CMS experiment at the CERN LHC, corresponding to an integrated luminosity of 1.52 nb(-1). The cross section is observed to rise rapidly at low WPb.N, and plateau above W-gamma N(Pb) approximate to 40 GeV, up to 400 GeV, entering a new regime of small Bjorken-x (approximate to 6 x 10(-5)) gluons being probed in a heavy nucleus. The observed energy dependence is not predicted by current quantum chromodynamic models.