Portland, Maine has a killer scene. If you are early stage you have everything you need here and can easily branch out if you get big enough.
I work at Bellhops in Chattanooga, TN. We were able to raise seed locally, and Series A and B from Bay Area and NYC investors while sizably growing market share. It definitely depends on what industry you're trying to start a company in but it's worked out pretty well for us.
Is Seattle considered an unusual location for a startup?
IIRC Wufoo from YC (which got acquired) was headquartered in Florida and had a remote team.
I don't know if you want to consider them a startup, but Dribbble[http://dribbble.com] is located in Salem, MA.