From the Wikipedia article linked to by Bo102010:

As late as 1996, there was still no universal association of one color with one party.[7] If anything, by 1996, color schemes were relatively mixed, as CNN, CBS, ABC, and The New York Times referred to Democratic states with the color blue and Republican ones as red, while Time Magazine and the Washington Post used an opposite scheme.

My memories from the time would have been formed mainly from television rather than printed sources, so there you go. (Although one printed memory that does stand out is, of all things, the French magazine L'Express, which used the Democrat-blue/Republican-red scheme in a 1996 article showing Clinton's 1992 victory.)