I think the majority of people would change their minds if a crime was commited and they caught the guy/girl who did it through surveillance.
That is why stores and airports already have their own cameras. They catch their crooks, and no one in those areas seem to care. If people have problems with camera's on the street, I hope they don't fly or shop.
Your exactly stating the reasons for why I don't think it's any problem to begin with. We already have them in malls, parking lots, grocery stores, heck even where I work has cameras. Why should you fear being watched if you're not doing anything wrong? If a city was to put up funds to have such camers in its' particular business districts then I really couldn't have any problem with it. Many cities/towns have cameras at stop lights as it is now.