reformat always fixes the problem although...
I am heavy into WoW, I read the forums all day at work and play when I get home. Since patch 2.1 ALOT of people are having FPS issues... I used to have 60 fps constant and now only in the outlands i have around 40fps. If you have less than 30fps with default video settings on that card then you should try reinstalling drivers or better yet reformat with a fresh system, I know alot of people try to stay away from reformatting though as it can be a pain. Make sure you have the latest OFFICIAL driver for your card. Also 2.1.2 (last tuesdays mini-patch) was supposed to fix alot of geographical errors although I didnt notice much of an increase.. It is a know problem at the moment that some people are getting lower fps ESPECIALLY in the outlands... So I would either wait till theres a fix or start reinstalling drivers.
Also use driver cleaner to get rid of any old files the drivers leave behind
If your currently using the latest official driver then you could try Omega Drivers http://www.omegadrivers.net
Edit: Another very common problem is if you are using additional addons the patches usually mess things up with them and cause stutter. disable all addons and see if that helps
Edit: here is a link from there tech support forum with a blizzard poster confirming low frame rate http://forums.worldofwarcraft.com/th...08244826&sid=1