How hot was it before you replaced the thermal paste? Can you verify that the fan is working? When your computer is "idle", what is the CPU load at?
Do you actually feel hot air blowing out? The app might be reading an incorrect value.
You could have a bad temp sensor. If you aren't feeling hot air coming out then you should be fine. At that high of temp your fan should be racing all the time. Is it?