Thank you for the insightful reply. However, I am not misremembering the story about the AA batteries. There was something in the original story about the third crime automatically getting elevated to a felony. So, yes, it needs to be a felony, but a minor third crime gets elevated to a felony.
I can't find the original 60 Minutes video, but here's a partial transcript of the episode (search for the word "batteries"):
And a book that recounts the same incident. The author is a Senior Fellow in Criminal Justice at the University of Southern California, so I assume he knows what he's talking about and has checked the accuracy of the story.
Actually, your transcript refers to a provision which elevates any theft (not any crime), with a prior theft, to a felony. This is a separate rule that predates and operates separately from the three-strikes law. (Though, obviously, before the reform to three strikes requiring the third felony to be violent or serious, had an interaction with it: but the conviction was, itself, a felony independently of the three-strikes law.)