Hobbits aren't (fully) Men either. No man could kill him, which he took to be immortality, but a Hobbit and a woman* could, unexpectedly.
Eh, technically Elves are no Men either. Or Gandalf.
Although, in the case of Gandalf, he does make a remark when Pippin says "Well, we have a mage. Just throw down a fireball and something", saying that the Witch King of Angmar can't be killed by living man, which does suggest some limit to Gandalf's ability, probably linked to the fact that he was in the guise of a man (and, as such, falling under the same rule as a "living man").
Scratch that. I don't have the book with me at the moment, but I think the scene with Gandalf and Pippin wasn't there and was made-up to explain to the people who didn't read the book the premise behind Glorifindels' prophecy.
By the way, I don't think the killing of the Witch King is supposed to serve as an example of prowess from Eowyn/a female (although I will admit that her being able to kill a Fellbeast can be considered a feat. She is also brave enough to stand by her king's side, knowing she risks death).
First and foremost - the participation of Eowyn is largely the product of the play on the phrase "no living man can kill me". Instead of using a child (or just a Hobbit, who isn't exactly a child, meaning it wouldn't count) he used a woman who is denied her plea to participate. She gets a support of a child-like non-human, because Eowyn being able to single-handedly kill the Witch King would've been too much, considering she had no special powers nor artifacts of her own. It also makes Peppin not useless.
The other part is, I think, showing what can happen to someone who wants to war, thinking it is all about having fun and glory. Eowyn manages to accomplish a great feat of defeating a powerful foe (with some help), but the cost is tremendous: her uncle, the king of Rohan, dies in her arms and she is likely to suffer psychological and magical wounds (similar to those felt by Frodo by being stabbed with the Blade of Morgul) for the rest of her life. Yes, she potentially did save Theoden from fate worse than death, and helped to turn the tide of battle (to some degree at least), but on personal level it's a pyrrhic victory.
To me it sounds more like a warning to all those sitting at home who are eager to go to battle for glory/adventure and are confronted with the ugly reality of war/combat/battle.