I've got a 3870 that's overclocked a little and I can run the game with almost everything on ultra smoothly. I've got e8500 and 4gb of ram and I'm usually using 75% of my CPU and 80% of my ram when playing that game so if you have less that 4 gb or a slow CPU that might be your problem.
I've got an older rig...(pentium firstname.lastname@example.org, 4gb ram, and radeon 3870x2), that i run in conjunction with my bigger gaming rig, and on the older one SC2 stutters a great deal when i run the game a recommended settings...the settings the game gives. I corrected it by lowering all settings to medium, even gpu dependent ones, screen res to 1280 x 1024, and turned down the sound channels from 64 to 32. That got rid of my probs. Now the only real problem i have is with lag on bnet cause of my dsl connection.