It does sound like a problem where this not enough space between the string and fret. If you can adjust the bridge with a small allen key (some bridges) this can raise the height by a fraction of a millimeter.
If you gently brush the string with your finger and work harder untill the buzz becomes noticable then it is most likley this. A new nut maybe? or if your bridge allows you can increase the gap.
If it is a new guitar then the chances are it wont be a problem with the frets or anything being loose on that, im certain that quality control would have picked that out within a second.
I had the exact problem with one of my acoustic guitars that I badly converted to a lefty. The nut was completley out and my option was to place two pennies behind the nut to increase the gap. BTW it sounds cr@p and i dont advise it to anyone.
