Short answer - depends.
Long answer - Well, now, there are a lot of variables here. First of all, acoustic or electric? How hard are you playing when it buzzes? How hard do you need it to play cleanly? Is it only on open strings, or is it everywhere? (You already answered that one, of course.) And, of course, there is always the old personal preference thing.
It is pretty normal for an electric guitar to buzz a bit when it isn't plugged in. A little bit of buzz that doesn't come through the amp is fine, and it can be set up with the action just a bit lower that way, which can be very helpful. Also, you can ALWAYS make a guitar buzz if you try hard enough. Don't go looking for buzzes; play normally, and see if they show up. It's a much more useful test for both you and the repair guy.
Of course, if it is buzzing even when you are playing very lightly, that will always be a problem, but if it only buzzes when you are playing a driving bluegrass bass run, it doesn't really matter if you are a new age fingerstyle player. Buzzes have a lot to do with the dynamics of your playing, and when the action is a bit higher, you can play a bit louder and still have it play cleanly. Then again, a very good repair guy I know (one of the best in the world, honestly) thinks that the guitar SHOULD buzz or about the last 5% of the dynamic range you plan to use. His theory is when you play that hard, you want it to sound a bit uncontrolled. I think he's nuts, but he has a lot of customers who love his setups.
So, should a guitar buzz? In my opinion, not when you are playing your normal style. But that doesn't mean never. Also, kudos to your repair shop. Everyone makes mistakes, but a good shop will fix them for free. I can't tell you how many horror stories I've heard from guys whose guitars weren't fixed somewhere, and then the shop wanted to charge them to fix it again. (Mind you, if I tell you it needs a fret dress to play right, and you ask me to just set it up, you are paying for the fret dress AND the set up when I am proved correct. I'm not responsible when you do not taking my advice!)
Gabriel