I, too, get the frightened "But my high school teacher said never to begin a sentence with..." reaction early on in the semester.  I usually  respond with "Well, let me tell you something about my family."  (They are totally confused at this point.)  
Then I  tell about how we trained our children never to talk to strangers.  I string it out and ham it up a bit, following one or other of the girls right through high school and college, noting when they somehow or other realized they could talk to a policeman or a doctor or...and then became confident enough approach a good looking boy in their algebra class...and finally  respond to a stranger at a singles bar.  
The class, of course,  gets caught up in the anecdotes and laughs at the right places.  Over and over I say things like "And we never changed the rule--and they never broke the rule."  By the end of all this they are totally ready to hear the punch line: "They never broke the rule because the rule never was 'Don't talk to strangers.'  The rule was 'Never get yourself into something that you can't get yourself out of--whether it's a conversation, a car, or a committee.'"
I end it all by saying "Your high school teachers know about standardized tests;  they know that more than half of the 'fragments' on those tests are simply subordinate clauses, and so  they teach you to recognize certain words that are danger signals .  When they tell you not to begin sentences with them, what they are really saying is (here I pause briefly, questioningly).  Almost every time students will respond, "Don't talk to strangers," after which I say "And that means?"  And someone will say "Don't get yourself into anything you can't get out of."  
I"ll praise them and start the lesson on how to get out of sentences that start with subordinate clauses.  
It's hammy--but it works--on several levels: it does not denigrate their former teachers, it introduces them to "college level" writing, and it gives them an example of symbolism and allegory I can use again later when we get to figurative language!