As Tony says some radiator flush could clear any blockage in the heater matrix. Could you disconnect the heater pipes and flush the heater with a garden hose both ways to see if any thing more comes out.
Also reading of some similar issues could need bleeding as they seem a pain to get all the air out of. I am sure the garage did a good job but here is one method.
How to bleed the cooling system.
1.Jack the front of the vehicle up onto stands as high as possible,
2.Turn the ignition on,engine off,heater on fan setting 1 and temperature fully hot,
3.Remove the rad cap/expansion cap,remove the bleed screw from the radiator and IF you have them the bleed screw(s) from the thermostat housing/top hose, return pipe or EGR thermostat.
4.Fill the radiator up and keep pouring till there are no more air bubbles coming out from the bleeds, using a funnel that fits tight in the radiator neck and filling it full of water will help push any troublesome air out, when good you can then install the bleeds and tighten down(don't snap them),ensure the rubber O-rings/seals are still on the screws/on the bleed holes.
5.Suck some water out so it's not full to the brim, replace the cap and then start the car. Run her up and check for heat from the vents when warm and check if over heating still persists. You may have to bleed troublesome cars twice(but rare).
6.If all is good then check the water level again in the morning when cool.
Don't give up on us yet we want to see you at one of the meets in the spring.