Based on your description of the symptoms, it's the nut. Looky here:
That angle in the 3rd example is exaggerated a bit for clarity. You want to split the difference between the flat string plane coming over the frets and the downward angle of the strings between the back of the nut and the tuners. It's a very subtle angle through the nut, but it makes all the difference between crappy tone and a nice clean ring.