I just read in the Minneapolis paper that Northwest Airlines will be starting a flight from Minneapolis to Paris nonstop. Not only will you be able to fly to Paris, but with Northwest's alliance with KLM/AirFrance it gives another way to get to Spain.

Mpls Newspaper

The new Northwest Airbus A-330's are the most comfortable coach class airplanes I have been on.