We just ran into this one today. We had an assy that would not allow any new mates to be added - the mate icon was grayed out. The problem was that the model was sitting on an exploded view configuration. In this case the explode was no longer valid because the part that was exploded wasn't even there. But that didn't seem to matter. The solution then was to do a right-click on that config and choose Collapse. Then mates were once again possible.
WT