I'd love to say that this was something that had been bothering me for a while, but unfortunately I too have just accepted the idiom without questioning it.

Apparently the reason a "red herring" is so called is that the strong smell of smoked herring was used to distract hunting dogs from the scent of their quarry.

In a million years of pondering, I'd never have come up with that...