King County is in the middle-of-fucking-nowhere-West-Texas, you see. That's how people vote there, or least have in the past couple of decades (before that, probably Democratic voters or at least lean)
In King County itself that's been true, but most of the area voted for Clinton, so there's a little more to the story than that.
There are three counties in the area that almost voted for Gore in 2000.
Foard County
2000 (556 votes) Bush 51%, Gore 47%
2004 (587 votes) Bush 59%, Kerry 40%
2008 (538 votes) McCain 61%, Obama 37%
Haskell County
2000 (2,927 votes) Bush 51%, Gore 48%
2004 (2,416 votes) Bush 64%, Kerry 36%
2008 (2,116 votes) McCain 66%, Obama 33%
Fisher County
2000 (1,872 votes) Bush 52%, Gore 47%
2004 (1,923 votes) Bush 60%, Kerry 39%
2008 (1,784 votes) McCain 61%, Obama 39%
Most southern conservatives gave up their "yellow dog democrat" voting patterns and started supporting Republicans in national elections a decade or two ago. Maybe this is just the last place in the south (or at least Texas) to give up the ghost on voting Democratic out of tradition rather than ideology?