I read some where that if you are pulling the guitar flat all of the time, it is the tuners and if it is going the other way it is the nut. You probably know that, which is why you asked, but throwing it out there if you didn't.
It does sound like the nut isn't slotted big enough. Be careful to not take out to much. It's really easier to dig a deeper groove while you are filing it wider.