The string is binding at the nut. The nut is the piece of plastic or some other hard material that is at the furthest end of the fingerboard, where fret number zero would be if there were one. The nut has six slots cut into it and the strings rest in the slots.
When you tighten a tuning machine, the tuning post pulls on the string which should slide through the nut so you are tightening the whole string. Sometimes the string gets stuck in the nut and when that happens, tuning up just pulls on the string between the tuning post and the nut, and the string itself (the sounding length) doesn't get tighter at all.
Eventually the tension on the little bit of string between the tuning post and the nut gets so high that it unsticks the string in the nut and the string slips through the nut, pulling the sounding length tighter and raising the pitch all at once. You probably hear a small "ping" sound when this happens.
Your strings might be sticking at the nut because they put larger strings on, and the nut slots are too small for the larger strings. That's possible, but is usually rare unless you specifically asked them to put especially large strings on. This is because most nut slots are made to accommodate a range of string sizes.
It is more likely that it's everyday friction causing the strings to stick. You just need to lubricate the nut slots. Here's how:
- Get a pencil with some soft-ish lead. #2 is fine, so is HB, B, F, 2B, 4B, any "B" pencil. A mechanical pencil with a fine point is best, but a regular wood pencil is fine - you want it to be very sharp!
- Loosen the all the strings by tuning them down until you can pull them out of the nut slots and move them to the side of the fretboard. Get them out of the way.
- Start with the high E strings slot (the smallest) and run the tip of the pencil along the slot. A lot of graphite dust will be left at the edges of the slot, but some will fall into the slot. After going back and forth a few times, move on to the next slot and repeat.
- Your pencil should be sharp enough that by the time you get to the D string slot, it might fit all the way in the slot and you can deposit graphite right on to the surface of the slot.
- On the low E slot, and maybe the A slot, you might have to rub the pencil tip around a bit to cover the slot surface with graphite.
- Put the strings back in place and tune them up a bit. Optionally use a good eraser to remove any excess graphite on the top of the nut. Tune the guitar up as normal.
If you get a good bit of graphite into the nut slots and the strings are still binding, then you should find a good guitar tech (obviously not the ones you've been taking it to already) who can cut the nut slots appropriately.
A quick workaround is to push on the bit of string between the nut and the tuning post every time you tighten the tuning machine to pull it through the nut. If you're tuning down, it can also stick. You might have to tug gently on the sounding length of the string to get it to slack off when tuning down.