In the UK every person has the right to take photos of other people in public places, so we don't have to ask for permission but I still feel incredibly rude for photographing people without asking.
Yesterday I went out photographing with a huge, clunky old Polaroid camera. Suddenly nobody cared if I was pointing the camera at them. It's weird - if I have my SLR with me, people notice, but if I have a small point&shoot, they don't care at all, and the same goes for a large Polaroid or even a Hasselblad. You have a normal feeling for a moment, then it passes. --More--
Speaking as some photographers' involuntary photography object, I say that's something you shouldn't get over :-) *Lunatic*, n. One whose delusions are out of fashion.
I spent yesterday evening persuading a room full of people to let me take shots of them for my friend for his birthday. It worked best when I joked with them, took a stupid shot and showed it to them saying surely they wanted to look better than that?! I don't think that would work in the street though! Ad astra per aspera