What are your computer specs? And does it always play at 15-20 fps, or does it slow down after a while?
Try downloading CCleaner, and run the registry scan and fix the errors it finds, I usually have to run it 3-4 times to get everything.
I am using an FX-8350 at 4.2ghz, an evga gtx 770, 8 gb ram, with an ocz vertex 3 ssd. I use CCleaner religiously so i don't think the registry is my problem. I did download the beta patch 3 from creative assembly, which seems to a have helped a tiny bit.
I have around 28 hours clocked in steam, i think it might have been faster when I had less discovered on the campaign map, i can't really remember now. I have read that Total War games are notoriously broken at launch.