Without seeing the guitar it's hard to say for certain, but it sounds a lot like you're gonna have to shim that nut. Depending on the material and quality of the nut you might need to buy a new one after taking the old one out. Sometimes they break as you do it.

To take it out get a razor blade, a small piece of wood and a hammer. Scratch around the edges with the razor blade first, then knock it out slowly, going from the fretboard side and hitting it and then around to the headstock side. Use the wood to cushion the hammer taps. Go back and forth till it's loose and then pull it out. You might need pliers.

Once that's done, find a piece of wood or metal to put underneath it to raise it up. Glue everything down with some kind of wood glue or whatever. Superglue will be a nightmare if the nut has to come off again, so don't use the firmest adhesive you can find. Just use something mild.

After you've done this--if you've been game enough--you can restring it and adjust the action at the bridge again.

Good luck. ;)