Geez...there's a lot of mythology running through this thread!
Bottom line: you got a bad setup. You took it back, they still didn't do it right - time to find someone who will. Any assessment here is speculation - you need to have the right balance of neck adjustment, bridge adjustment, & nut for it to play correctly, and without actually seeing it there's no way anyone's advice can be taken as gospel - EXCEPT the fact that it's not right now, and you need to find a good tech to fix it or learn to do it yourself.
I just started doing my own guitars (after playing for almost 30 years) & it's not that hard, once you have the tools & follow a good procedure. I used the
Guitar Player Repair Guide by Dan Erlewine, and worked off of the basic factory setups he lists for Fender & Gibson for my guitars, and they came out great.
One thing he talks about is setting your neck straight, with little or no relief, & your action high. I was always a low-as-you-can person until I tried this approach - I found that it really brought out the tone of my guitars, though! The basic idea is that a straight neck improves the acoustic resonance of the instrument. This necessitates raising the action to get rid of fret buzz - the neck relief is a sort of cheat to get around this & drop the action - but really, it's not that bad once you get used to it, and the improvement in tone is well worth it IMHO.
Bonus tips: for you guys who don't use locking pegs (my PRS has them, but not my other guitars) what you really want to do when re-stringing is to pull the string through the peghead, and then bend the string back against the direction of the wind, i.e. if the peg is going clockwise, bend the string end counter-clockwise. This gives the peghead something to grab onto, so the string won't slip back through the hole under tension. I usually leave enough slack for 1 1/2-2 wraps around, which has always been sufficient to hold it in place. And yeah, stretch your new strings. I give them a tug from the middle, like drawing a bow, and then run the "pull" from bridge to nut a couple times. This usually stretches them enough to stay 99% stable - play on 'em for a short time (20 minutes, maybe) & they'll work themselves in.