Who ARE these teachers who spread this stuff and why don't/didn't they ever check their own facts?
The Chicago Manual of Style, Garner's Modern American Usage, Fowler's New English Usage, the American Heritage Dictionary, and the simple logic of grammar and idiom all say it's fine to start a sentence with "and" (or "but" or "so"). I don't know of any real authority that disagrees.
It's a shame how powerful misinformation can be.