Tennessee (and Kentucky) was the most Whig state in the country. I don't think it ever voted Democrat until the GOP was founded.
Oh, no- it certainly went for Andrew Jackson- all three times, and overwhelmingly. In 1836, when New Yorker Van Buren was the Dem nominee, there was one of two Whigs running in the general, Hugh White who was from Tennessee. So part of it may have been that White pulled many Jacksonian Democrats away from the Dems.
1. Jackson was an exception. That's like saying "Massachusetts isn't a Democratic state, it went twice for Reagan".
2. The Whig party didn't effectively come into existence until after Jackson disappeared from the scene, so it doesn't count for that reason as well.
EDIT: The Democrats lost Tennessee in every election 1836-1852, that is, during the entire time the Whigs actually existed as a real political force. I rest my case.