North Dakota makes some sense.
Eastern North Dakota is pretty similar to rural areas of Western Minnesota - rural, more progressive Scandanavians. IIRC Socialism was pretty popular here in the early 1900s. They even had a similar state-level party to the Minnesota DFL in the form of their
Democratic Nonpartisan League. You can see from his map that Obama actually won some of the areas around Fargo and Grand Forks. In 2008 North Dakota had two highly popular Democratic Senators. The reason the state has shifted so far right in the last decade is the Bakken boom has not only brought in lots of oil workers from outside the state but also made a lot of the entire state economy heavily dependent on oil.
South Dakota in 2008 has some similarities - similar demographics in the Eastern part of the state (but not as strong), Democratic Senator and only four years removed from being removed by Tom Daschle, lots of votes on the table in the reservations.