Based on benchmarks, I should be able to run Skyrim at around 30-40fps right out of the box on Ultra settings, but even High settings are giving me frame rates around 15-25. My GPU is at 99% usage when I'm playing, but my i7 2600K (3.4GHz not overclocked yet) is only using 4 out of 8 cores at about 40% each.
When I lowered the resolution from my screen native of 1920x1200, frame rates jumped up, which seems to point to the GPU, but I don't know for sure. I have 8GB of memory, but I don't think that's the culprit if Skyrim can only use up to 4gb with the proper patch.
I had the same problem and I managed to get ~45fps by turning AA down to 2 or 4x. There's likely a better way to do it without sacrificing the graphics but so far this works best for me and I'm still running other settings on High-Ultra.
I don't think 6850 can do ultra at high fps for skyrim. 5850/6870 is about the minimum, and they would only get like 30-45ish fps at 1080p. You can either set it on high, set it on ultra and lower a few settings, or upgrade the card. You also might want to check skyrimnexus, there might be something there that would make the game run a bit more smooth for you.