Warning signs for tipping points (or critical transitions) have been very actively studied. Although the theory has been applied successfully in models and in experiments, for many complex systems, e.g., for tipping in climate systems, there are ongoing debates, when warning signs can be extracted from data. In this work, we provide an explanation, why these difficulties occur, and we significantly advance the general theory of warning signs for nonlinear stochastic dynamics. A key scenario deals with stochastic systems approaching a bifurcation point dynamically upon slow parameter variation. The stochastic fluctuations are generically able to probe the dynamics near a deterministic attractor to detect critical slowing down. Using scaling laws, one can then anticipate the distance to a bifurcation. Previous warning signs results assume that the noise is Markovian, most often even white. Here we study warning signs for non-Markovian systems including colored noise and $alpha$-regular Volterra processes (of which fractional Brownian motion and the Rosenblatt process are special cases). We prove that early-warning scaling laws can disappear completely or drastically change their exponent based upon the parameters controlling the noise process. This provides a clear explanation, why applying standard warning signs results to reduced models of complex systems may not agree with data-driven studies. We demonstrate our results numerically in the context of a box model of the Atlantic Meridional Overturning Circulation (AMOC).