The problem with paid parking at least in North America is that many/most cities are designed so that you need a car to get around -- driving is a necessity not a luxury. This makes paid parking feel like a tax rather than a service.

Contrast that to, say, a dense city like Tokyo or Beijing where parking is both scarce and almost always comes at a cost. There is much less backlash, because you can get to pretty much everywhere just using public transit. In this case, people accept that point-to-point driving is a luxury -- you're choosing convenience so it's natural that that would come at a cost.