Here is the CPU and Crystal that come with the mpguino. It is pin compatible but some of the instructions/register names are a bit different than the mega8. I'm moving towards 20mhz too FYI, couple low level timing changes as you can imagine.
I don't think it will solve slow 32 bit math though, 32 bit math is handy, but slow, have to use it sparingly. I do a lot of it but only once every 1/2 second to update the display and just do basic addition in the interrupts.
$4.11 atmega168p
http://mouser.com/Search/ProductDeta...ATMEGA168-20PU
$0.57 20mhz small crystal
http://mouser.com/Search/ProductDeta...-FOXS200-20-LF
edit: did not see a divide assembler instruction for either the mega8 or 168. Both muls take 2 cycles