Good luck. Is it the shifter for sure? If there's no tension, it could be the cable as well, or where the cable attaches on either end. From your description, it doesn't sound like these clowns did any diagnostic work to determine what the actual problem is. If something was too tight (in their estimation), and they loosened it, then it seems less likely that something's broken - more likely that something's come loose enough that it disengaged. That would require a readjustment rather than a new part.
It's impossible to do more than blindly guess, though, without knowing what they adjusted. It's possible this is a quick and easy fix. Don't know what kind of warranty you have, but I'd prefer to be dealing with a shop that actually knows something about bikes.