This has happened twice now. With the 2013 Governor race and today. Virginia is a purple state, and it shows in almost all its elections. Add that with the wave affect and Warner almost lost his job.
I think what we're seeing a textbook example of the "boom/bust" coalition that hurts Democrats so poorly in off-year elections.
In presidential years, Virginia is a "lean Democrat" state but reverts into "pure tossup" category anytime there's not Obama on the ticket to prop-up African-American, Hispanic and youth turnout. Of course, this happens in every state but it seems like an especially strong phenomenon in Virginia for whatever reason.