We consider a fundamental remote state estimation problem of discrete-time linear time-invariant (LTI) systems. A smart sensor forwards its local state estimate to a remote estimator over a time-correlated multi-state Markov fading channel, where the packet drop probability is time-varying and depends on the current fading channel state. We establish a necessary and sufficient condition for mean-square stability of the remote estimation error covariance in terms of the state transition matrix of the LTI system, the packet drop probabilities in different channel states, and the transition probability matrix of the Markov channel states. To derive this result, we propose a novel estimation-cycle based approach, and provide new elementwise bounds of matrix powers. The stability condition is verified by numerical results, and is shown more effective than existing sufficient conditions in the literature.We observe that the stability region in terms of the packet drop probabilities in different channel states can either be convex or non-convex depending on the transition probability matrix of the Markov channel states. Our numerical results suggest that the stability conditions for remote estimation may coincide for setups with a smart sensor and with a conventional one (which sends raw measurements to the remote estimator), though the smart sensor setup achieves a better estimation performance.