Yep looks like it, you may get 3-4°C more (if that) so unless your airflow is able to be improved (or you go for a different cooler) I guess it's going to be "normal". I'm a little concerned about the temperature probe, where exactly is it mounted?
You should clean off the old (I use a cotton bud, Q-Tip ? and isopropyl alcohol) and apply new every time you seperate the cpu and heatsink.
On page 1, post number 9 (
click here) is a link to the instructions on how to apply AS5 to his cpu.
EDIT: For the benefit of others who may read this the application method linked earlier and above are for the OP's P4 cpu, the methods for dualcore and quadcore cpu's are different, you can navigate to them from the link below
LINK