That seems like a pretty good decrease for just having swapped out the paste, so it's probably working fine. I'd imagine your issue is with the cooler itself, maybe you are doing something that's CPU intensive but the cooler isn't up to the task of maintaining low temperatures. What CPU is it, and are you using the stock cooler?