There may be a need to dress the frets, but that is a simple procedure at a good shop however the symptom is usually a buzzing or dead spot over a few specific frets. this matches part of the description of your problem. My brand new Epi Tbird Pro-V played like a whole different instrument after I had the frets dressed and the edges filed. The finish on that instrument had left a lot to be desired.
The truss rod sets the neck bow. Usually if neck bow is out you will notice buzz more in one half of the neck than the other. Since you trust your shop we'll assume that's OK for now.
The bridge saddles set the string height, it's odd, but not impossible that all of the saddles need adjusting. String height is measured at the 12th fret and should be 5/64th treble side and 7/64th bass side (Source: http://www2.gibson.com/Support/Tech-...ion-Guide.aspx
) . You might check the string height next.