Temporal broadening of pulsar signals results from electron density fluctuations in the interstellar medium that cause the radiation to travel along paths of different lengths. The theory of Gaussian fluctuations predicts that the pulse temporal broadening should scale with the wavelength as lambda(4) and with the dispersion measure (DM; proportional to the distance to the pulsar) as DM2. However, for large dispersion measures, DM > 20 pc cm(-3), the observed scaling is lambda(4)DM(4), contradicting the conventional theory. Although the problem has existed for 30 years, there has been no resolution to this paradox. We suggest that scintillations for distant pulsars are caused by non-Gaussian, spatially intermittent density fluctuations with a power-law like probability distribution. Such a probability distribution does not have a second moment, and therefore the previously applied conventional Fokker-Planck theory does not hold. Instead, we propose to apply the theory of Levy distributions (so-called Levy flights). We show that the observed scaling is recovered for large DM if the density differences, DeltaN, have Levy distribution decaying as \DeltaN\(-5/3). In the thin-screen approximation, the corresponding tail of the time-profile of the arriving signal is estimated to be I(tau) proportional to tau(-4/3).