Soft phase lags, in which X-ray pulses in lower energy bands arrive later than pulses in higher energy bands, have been observed in nearly all accretion-powered millisecond pulsars, but their origin remains an open question. In a study of the 2.5 ms accretion-powered pulsar SAX J1808.4-3658, we report that the magnitude of these lags is strongly dependent on the accretion rate. During the brightest stage of the outbursts from this source, the lags increase in magnitude as the accretion rate drops; when the outbursts enter their dimmer flaring-tail stage, the relationship reverses. We evaluate this complex dependence in the context of two theoretical models for the lags, one relying on the scattering of photons by the accretion disk and the other invoking a two-component model for the photon emission. In both cases, the turnover suggests that we are observing the source transitioning into the propeller accretion regime.