777spaceman hit the high points. If you are still having difficulty figuring out what is going on, I suggest selecting "Detailed List" as the Action in the Check/Merge Coincident dialog menu. It will tell you more about why 2 nodes cannot be merged.
could loads/constraints be applied to both nodes ?
it sounds like either
1) both nodes are undeletable ('cause they're being used for something like loads or constraints), or
2) maybe your coincident node check says to delete a specific node (lower, higher, ...) and that one is undeletable ?