Your vaguely remembered "rule" may well have been issued by a harried English teacher in fourth grade who was trying to stop her students starting every sentence with "But then .." or "And then .. ".
But starting a sentence with a coordinating conjunction is often exactly the right choice.
There is a discussion of this and other "zombie rules" on Language Log. Here is what linguist Mark Liberman has to say:
There is nothing in the grammar of the English language to support a prescription against starting a sentence with and or but --- nothing in the norms of speaking and nothing in the usage of the best writers over the entire history of the literary language. Like all languages, English is full of mechanisms to promote coherence by linking a sentence with its discourse context, and on any sensible evaluation, this is a Good Thing. Whoever invented the rule against sentence-intitial and and but, with its preposterous justification in terms of an alleged defect in sentential "completeness", must have had a tin ear and a dull mind. Nevertheless, this stupid made-up rule has infected the culture so thoroughly that 60% of the American Heritage Dictionary's (sensible and well-educated) usage panel accepts it to some degree.