I used Nokian all seasons about 5 years ago. The new all seasons are said to be much better than the ones I used, I've heard really good things about them. The Nokians of old I found to be a good tire in the snow (for not being a dedicated snow tire), but pretty lousy in the summer. I have a Mazda 3 and run dedicated snow tires in the winter (Minnesota). It is an investment up front yes, but well worth it to have sticky summer rubber in a larger, wider size, and snows that are smaller and narrower. The summer tires last as long as an all season would (with a lower treadwear rating) because I don't run them all year. Winter tires last about 3 years (for me) until they're not really competent for winter use.
Besides the Nokians, I've heard good things about the General Altimax (but that may be more to how cheap they are) and the Michelin Premier. The Continental PureContact are getting great reviews, but I have no experience with them (and don't know anyone that has used them).