Calm down, it's not a problem. Your computer will not explode.
First, what processor are you using (Intel P4, AMD athlon, athlon 64). If your temperature ratings are correct, I'd say it's a P4 or athlon 64. For those systems 20 to 40 C might be normal, provided that the 20C is at startup, and it levels out around 30C. My P4 (2.6c) starts at 20, room temperature, goes up to 30, idle temperature, and jumps to 40 to 45 during stress situations.
The 35-40 C motherboard temperature isn't measured in the environment of the processor. Generally, it's a measurement of the computer's chipset, which tends to get as hot as that. (That's the reason they have a heatsink on there.)
As for the drop in temperature after replacing the cooler: perhaps your cooler wasn't placed properly the first time, or your replacing it improved the fit. It happens.
