And I thought a red herring was a matjes herring!!!

From: The Phrase Finder

The meaning and origin of the expression: "Neither fish nor flesh, nor good red herring"

Meaning

A deliberate misleading and diverting of attention from the real issue.

Origin

Red herrings are salted herrings that turn a reddish colour during the smoking process. They have come to be synonymous with the deliberate false trails that are the stock in trade of 'who done it' thrillers.

The term has been used to refer to people as well as to fish for some centuries. John Heywood's 1546 glossary, A dialogue conteinyng the nomber in effect of all the prouerbes in the Englishe tongue includes the expression:

She is nother fyshe nor fleshe, nor good red hearyng.

Fish was eaten by the clergy, flesh by the rich and the dried and smoked herrings by the poor. So this list of the foods eaten by all classes of society was a metaphor for 'encompassing all eventualities'.

How do we move from the actual herrings in that expression to the figurative 'throwing off the scent' meaning? One theory has it that the meaning derives from the practice of using the oily and smelly herrings to lay false trails for hunting dogs. This practice is well documented from as far back as the late 1600s and Nicholas Cox's The Sportsman's Dictionary: Or The Gentleman's Companion, 1686 describes it:

"The trailing or dragging of a dead Cat, or Fox, (and in case of necessity a Red-Herring) three or four miles... and then laying the Dogs on the scent."

It seems implausible that people laid false 'fishy' trails in order to deceive hounds so that their prey would escape. After all, there was no hunt saboteur movement in 1686, and who would have a motive to do that? It's more likely that the use of red herrings was a training exercise, intended to put the hounds on the scent rather than to throw them off it. Nevertheless, the laying of a scent trail for dogs does establish the linguistic 'surrogate' meaning for 'red herring' and the further step to 'deliberate deceit' isn't a large one.

Another theory is that the meaning derives from a trick played on one of his servants by the wealthy English clergyman Jasper Mayne. Mayne died in 1672 and willed large sums for the rebuilding of St Paul's Cathedral and to the poor people of his parishes of Cassington and Pyrton. He also willed to a servant "Somewhat that would make him Drink after his Death", which was left in a large trunk. When the trunk was opened the servant was disappointed to find that the bequest turned out to be a salted herring. The will doesn't mention a 'red herring', but a report of the event in Jacob's Poetical Register, 1719, does, so we can date the 'false representation' meaning to that date at the latest.

Of the two theories, the Mayne story seems the more compelling. It introduces the idea of a deliberate misdirection, which, unless we are to believe that people deliberately misdirected hounds, the other lacks.

Whatever the source, the figurative usage of the phrase was well established in UK by the early 1800s and had migrated to the USA by the middle of the century, as in this example from The New York Times, in May 1864:

But when the Emperor found that England would not join him in a war, he cleverly started the "red herring" of the Congress which he knew well enough was out of the question, but which has admirably answered his purpose of creating a diversion.

Source: http://www.phrases.org.uk/meanings/red-herring.html