Having lived in New Hampshire and Vermont and having gotten married in Maine and visited many times, I think you should add all three to the list. They are all remarkable in their own ways. I would really recommend that you not cross NH and VT off your list. They are wonderful places of natural beauty -- especially the rolling Green Mountains of Vermont and the more impressive White Mountains of New Hampshire. I think you would love them both.
As a side note, I honeymooned in Iceland, and would recommend that if you go again, you get out and see the country beyond Keflavik and Reykjavik. There is some wondrous natural beauty out there and some great places to hike and just look around. Waterfalls, amazing ones, abound!
Yeah, the upper New England teir is back on my list. At least Maine and Vermont. NH.. maybe if you drag me over there somehow. ;-) Actually, as a big Julian May fan, I need to visit NH at some point.
Iceland: Too expensive for me. :-(