Depends on a bunch of factors, but CPU use will spike when you open a program - which may play through to an increase in temperature.
20'C of a spike seems excessive to me though.
How did you idle temps look before you re-applied the paste? You're sure you seated the cooler correctly?