This paper investigates the stability of Kalman filtering over Gilbert-Elliott channels where the random packet drop follows a time-homogeneous two-state Markov chain whose state transition is determined by a pair of failure and recovery rates. First, we establish a relaxed condition guaranteeing peak-covariance stability described by an inequality in terms of the spectral radius of the system matrix and transition probabilities of the Markov chain. We show that this condition can be rewritten as a linear matrix inequality feasibility problem. Next, we prove that the peak-covariance stability implies mean-square stability, if the system matrix has no defective eigenvalues on the unit circle. This implication holds for any random packet drop process, and is thus not restricted to Gilbert-Elliott channels. We prove that there exists a critical curve in the failure-recovery rate plane, below which the Kalman filter is mean-square stable and above is unstable for some initial values. Finally, a lower bound for this critical failure rate is obtained making use of the relationship we establish between the two stability criteria, based on an approximate relaxation of the system matrix.