Will you need a new cooler? Probably. It depends on if and how much you are upgrading.
If you are just replacing a bad CPU with another of the same make and model, then maybe not. But then you have to know why the original one went bad. If it went bad due to overheating then your cooler was insufficient to begin with.
If you are upgrading, say from a2 or 4 core to a 6 or 8 core, then yes you will need a better cooler. Or if you are upgrading to a higher clock rate or plan on overclocking the new one.
CPU's have a specification called TDP or Thermal Design Power which is an indication of how much cooling you'll need. Compare the TDP of your current CPU to that of the new CPU to determine if you'll need better cooling.
Some CPU's come with a cooler but the coolers are typically at the low range of the TDP so if you plan on overclocking or a heavy workload you'll need better cooling. These are usually called "boxed" CPU's. It never hurts to have more cooling than you need. You can also buy stand alone CPU's that don't come with a cooler for a little less if you are going to buy better cooling than is provided in the box..
Keep in mind that you have to also get that heat out of the case so you might also need more/larger/bigger case fans.
There are several good PSU calculator programs on the net that will estimate how much power you need. Here's one:
http://support.asus.com/PowerSupply.aspx?SLanguage=en