I have had exactly that experience. This upgrading to the M-patch (from the J-patch) the CPU's thinkingtime between turns started taking aprox. 5 times longer. When I get to around turn 300 on a huge map with 11 civs, my average in between turn time is 3 minutes, whereas before the patch upgrade, it never took more than 30 seconds.
Can anything be done? Apart from buying a new computer ;-) I have a save game from around turn 300, if it helps.
Razzle
