Red herring is a very old figure of speech. I remember reading that it was originally referred to an alleged scheme to confuse dogs on the trail of a criminal by dragging a red herring across the trail to divert the dogs.I never heard any explanation why the herring should be red.

I found one URL giving some examples.

http:// www.nizkor.org/features/fallacies/red-herring.html