Howard Dean:

"I want to be the guy for people with pickup trucks and confederation flags."

I don't actually know the history of the political colors in the US. But I have a strong hunch the red-blue business is historically "shallow". As far as I can see, the only significance this color code has is in marking electoral maps on TV and the internet. (The generalizaton to "red states" and "blue states" is fairly recent for sure.) So my guess is this code may not even predate the era of TV. The political colors in Europe, on the other hand, go back to the 19th century, and they have a much wider currency. Black is the color of the (catholic) church; that's where the conservatives got it from. Red has been the color of the socialist movement from its inception. I don't know why they went for red, but a good guess is they wanted something as different from the conservative color as possible.

If you can't convince them, confuse them. (Harry S. Truman)

I do believe that the current Red/Blue breakdown is only around a decade old (though it has taken root like an old oak tree).  And it is reversed from what it should be.  I like the British system, with Red for Labour and Blue for the Tories.