I was wondering if there is a difference if you add that ん. Is the first one correct and the second one not?
I think the difference is how long you assumed that the person is a man. 「男じゃないんですか？」 implies that you've been assuming that the person is a man for some time. On the other hand, 「男じゃないですか？」 implies that you have just realized that the person is a man (though, it depends on the emphasis. You would put the emphasis on the word 「ない」 in this case).