Is it really much of a mystery at all?
A lot of issues are met with the mindset of "It would never happen to me". Terrorists blowing something up make the front pages, so people think it might happen to them (even though the odds of it are tiny). Slow erosions of civil liberties usually do not make the front pages, so people don't pay much attention and assume that only bad people are going to be arrested, denied due process, shot, or otherwise the victim of a resulting injustice.
A lot of issues related to freedoms and civil rights also take second place to much more immediate practical concerns, particularly in an economic downturn, like whether your kid has a good school to go to, or whether your parent gets looked after properly at hospital. The old "It's the economy, stupid" line is as true in politics today as it ever was.
To be fair, it is also true in the West today that just as the risk of being a victim of terrorism is low, so the risk of being a victim of government abuse or incompetence in applying these anti-terrorism measures is also low. A rational and objective citizen looking at the practical reality right now might consider that neither issue is that significant and there really are much more important things to worry about.
The strongest arguments for promoting civil liberties and reducing government powers are generally those of equality (just because something bad is unlikely to happen to you, it doesn't mean it's unlikely to happen to someone equally innocent but in a less fortunate position) and long term risk (just because today's governments and security services and police forces don't routinely abuse these capabilities and legal powers on a wide scale, that does not mean tomorrow's won't, and history shows that the risk of such abuse is real and the consequences can be catastrophic).