I see stuff like this all the time at my shop. Sounds like you got lucky and they at least changed the HDMI port correctly...usually that's the part they screw up. Anyway, given that it overheats so quickly it's likely that they didn't take the time to clean the old thermal paste off and put new thermal paste in. There's no way for me to know for sure since I don't have it here to test...just going off of what I've seen a lot of.
It's also possible that the thermal pads are out of place or doubled up. This can cause the motherboard to not sit completely down against the heat sink like it should which would cause it to not make good contact with the thermal paste and heat sink.
I agree that you shouldn't take it back to the place that "fixed" it. Normally I would give a repair shop the benefit of the doubt but it's clear that the people you took it to are crooks. I've got teardown videos and overheating videos on my Youtube channel and there are lots of other good ones out there too so you could probably take it apart yourself but if you're not comfortable with that you may want to send it in for repair.
Hope this helps.