I've never done any serious street photography. From doing some reading on the subject, you basically need to be extremely confident in what you are doing. If you are furtive and timid, you end up looking like a perv.
Beyond your own issues, the next hurdle is to not get arrested for doing something that is entirely legal and the source of a lot of great art.