First, offer to add "video surveillance" signs outside and inside the elevator(s).
Second, similar to Jeff K's comment, all depend how it's sold to the organization.
The company I work for is psudo-gov't with 8 unions. To get something like this through, you need to establish trust that it's a passive camera and viewed when required (unless you're trying to catch people in the act).
Specifically, use the position that it'll be used for life-safety (check on well-being of persons if trapped) or post-incident investigations (see who vandalized). You're also setting the stage to protect the company and employees in a harassment claim. Female employee says in appropriate advances were made, pull the tape to find out and save a lawsuit for dismassal without cause.
Essentially, when dealing with privacy and employee groups, reassure them it's for their benefit, you're not trying to hide anything and explain "we've got better things to do the watch people ride elevators".
Vandalism aside, if something happens, they'll be happy it was there.