I suppose similar reasoning is how we arrive at our judgements on most questions of legality, personally, when deciding how to behave and what to worry about others doing day-to-day. Like, I definitely can't show you the statute that says driving the wrong way on the highway is illegal, rather than just a very bad idea, and I'm not sure I've even ever been told specifically that that is illegal let alone done the research to makes sure it's illegal—but nonetheless, I'm pretty sure it is. So, I would guess some people surprised that their cell phones spy on them in certain ways are more surprised that they are being used that way and not that they could be used that way.
[EDIT] to stretch the analogy further, if I were surprised to learn that some delivery company had found a way to reduce delivery times by driving the wrong way on the highway, the fact that vehicles are technically capable of driving the wrong way on the highway wouldn't be the part that I found surprising.
In the specific case of tracking/spying I'd imagine lots of people (not most, but many) have considered the possibility, then dismissed it without looking into it any further because it seems like something that would obviously already be illegal, and assuming things that seem like they ought to already be illegal are already illegal often gets one to the correct conclusion—just not this time. Those sorts probably assume that if a law enforcement agency gets a warrant or something then they might start tracking locations using cell phones, but not that the cell phone company is already doing that 100% of the time to everyone, since, again, it really seems like something that'd be illegal. I think a lot of the "information economy" falls in this blind spot—that credit card companies would be selling your purchase history or google/your-ISP would be recording every single website you visit also seem, intuitively, like things that'd be very illegal, for example.