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.