Maybe it's because I live in Madison and only hear the anger directed at Walker, but I never got the impression the current budget is particularly popular. One of the fastest ways a Republican can tick off squishy moderates is by cutting funding to education. I agree he'd probably be down in Wisconsin without that, but down 12 is a lot. Wisconsin, like most states, is more Democratic in presidential elections than midterms, but I don't see any reason why that trend would be particularly strong here compared to other places. If anything I'd expect it to be less important since we're such a high turnout state in general.
If Scott Walker's recall election was on November 6, 2012, do you really think he would've survived (even against the rather weak Tom Barrett)? Admittedly, there probably was a minority of largely centrist voters that rejected the notion of a recall for political reasons. Scott Walker won by about 170k votes with 2.5m voters in that election. However, President Obama won by over 210k with 3m voters and Tammy Baldwin won by almost 170k with roughly the same 3m voters.
Even beyond Wisconsin's typically high turnout, I think there is something fundamentally different in a presidential election compared with any other election. It seems like there's also a change in the very attitude of the electorate. If Scott Walker had to face a recall election on the same ballot as President Obama, I think his removal from office would have been successful.