From all the comments, it seems as though it is a game problem. However I thought I would just post what happened to me, and maybe a few of you are in the same boat.
I was constantly getting 10-15 FPS, no matter what settings. I have a Q6600 (not the best I know) 8gb RAM, and a GTX 580. So its not the best system, but it certainly should run the game on low-med settings. I came here weeks ago, and just presumed I had the same problem as everyone else, and have been following this thread closely ever since. A few days ago, I was looking in my BIOS, and a power saving setting called ce1 (I think) was on. This actively under-clocked the CPU. I disabled it, and I got a fairly sizable FPS increase to around 30-35 FPS. I have since overclocked the CPU and added better cooling, and am now getting ~45 FPS on max settings, no matter where I go.
I get that this won’t help everyone, but it might help a couple of you.