You may actually be able to go to a core 2 duo. You can pick up a core 2 duo for around 20 bucks if you poke around.
The concern would indeed be cooling. You should be able to fit most any aftermarket cooler on there. Another concern would be that the motherboard will not handle the jump from a 35w to 65w chip.
On the other hand, we're talking about 6 year old chips here. It might be time to consider an upgrade.