I'm American, and so almost all of the Russian people I know are ex-Soviets, most of whom are very traditional and many of whom have impeccable manners. As such, I think that I may have an overblown view of how often people refer to others using their отчество (patronym?). Is it actually still frequently used in places like schools and at work? Also, when referring to someone you don't know (i.e. when the news is talking about someone in a story, when giving a presentation about someone, etc.) would you include their отчество? I have a feeling that things like this may have fallen out of style since the fall of the Soviet Union, but don't know anyone who would be able to tell me.
EDIT: Thank you all very much for your answers! I appreciate all of them, and the breadth of information all of you gave me. I probably should have specified that although I am American, Russian is my first language and I was raised in a Russian neighborhood. Because of this, I know pretty well the differences between "ты" vs "вы" and also a lot of the easy cases when you would use someones отчество. With this in mind, I chose shabunc's answer, as it was closest to my original intention for the question, but Sandra's and everyone else's answers are all also very helpful!