yep, they must have screwed up. I guess you could just take it back there and tell them to fix it.
Though it does take a while for thermal paste to settle down and start working better, putting new thermal paste shouldn't cause a huge increase in temps.
Double check they pluged the CPU fan header back onto the motherboard. Perhaps they completely forgot to plug in the fan. (lol, did it a few times myself).
Anyway, I'd double check with them and see what compound they've used, coz you do need some decent stuff nowadays, bog standard white silicon based TIM was good enough in the days of P1 MMX's, AMD K5's and Cyrix M2's, not for AMD FX70's Pentium 4 D's and the likes.
If you've seen my other posts on this subject just ignore them I cant see my posts and have to search for them for some reason. Thats why I posted over and over. Okay I have p4 its plugged in and the thermal paste is called dynex