First off, Republicans massively overplayed (and overplay) the supposed "Republican swing" that has been happening in Minnesota recently. This is not the case. Minnesota moderated, but it didn't Republicanize, due to a recent boom in suburbs. But now our suburbs are getting older (my 'burb included
) and are going the opposite way, from staunchly Republican again towards the middle. It's also important to note that Minnesota's Republicans are not the conservative types found elsewhere... they tend to support a strong public school system and more public health care (Pawlenty, for instance, opened a program to get prescription drugs from Canada). [propaganda] Not coincidentally, Minnesota always ranks among the highest in educational achievement and in quality of health [/propaganda]
Second, Coleman's election was basically a fluke. First in 2002, Wellstone died, which was unfortunate, because we was quite liked in the state. So, the state DFL got Mondale out of retirement or whatever he was in... not the best choice, but IMO not horrible either. Unfortunately, Wellstone's funeral was used as a campaign rally, pretty much (by Wellstone's sons, no less!); several dignitaries left, including then-Governor Ventura, who was among the many attacked by Wellstone's sons. Predictable, Mondale's numbers fell after that incident. Coleman went on to win. 2002 wasn't a good year for DFL in general; Republicans ended up controlling the state house 81-53.
Third, to add to what Trondheim said, third parties have a strong tradition here. The Farmer-Labor Party of the past was very successful, and the Reform Party (later the Independence Party) was successful in 1998 with Ventura. The Green Party too is very strong; they got over 5% in 2000. So, the Greens are why Gore did so 'poorly' in 2000, as most of them went over to Kerry in 2004.