Here's one idea I've seen bandied about at...gosh, can't remember when. In essence, you allow every county, every dozen years, say, to decide which state it wants to belong to. This would of course require a pretty extensive rewrite of federal laws about how cross-state crimes and federal jurisdiction are handled, because now the boundaries are smaller, but it fixes the problem that we currently have several states which, although they were natural states at their founding, are divided into regions that hate each others' guts. I grew up, for example, in Pittsylvania County, in south-central Virginia- a wonderful place in the way that small, rural places with salt-of-the-earth people tend to be, but pretty conservative. (Its congressional district was a swing district due to the inclusion of Charlottesville, but until... '06, I think, was represented by none other than the wild, wacky, lovable Virgil Hamlin Goode, Junior). Virginia is divided into two parts: a conservative, Southern, not all that rich rural area, and a northern, liberal, wealthy area around DC and stretching down the east coast. Both parts hate each others' guts, for good reason, I should add. There are several other states like this- Missouri, Georgia, even Florida and Pennsylvania.
There is really no good reason why these regions of the country should be forced together when they'd both be a lot happier choosing their own policies.