What happens when you set the graphics options to low?
I set it to medium and i get 30-35fps, and i'm not recording i'm monitoring. Wierd huh? Anyways, I googled harder and found that the latest drivers for Nvidia cards right now (301.72) is having much issues, after reverting to an older one (285.XX) I'm getting better fps.
I used to get 12 fps on the SC2 login menu, and now it's back up to 60+.