So I'm trying to remember if the Witch-King ever proved to be actually be a witch.
The only time I remember him doing any magic was in the controvertial extended scene of ROTK where he breaks Gandalf's staff, which doesn't even happen in the books.
Did he ever use any kind of magic?
Depends on how you define "magic". One very clear instance, I think, was at the assault on Minas Tirith:
Then the Black Captain [i.e. the Witch-king] rose in his stirrups and cried aloud in a dreadful voice, speaking in some forgotten tongue words of power and terror to rend both heart and stone. Thrice he cried. Thrice the great ram [Grond] boomed. And suddenly upon the last stroke the Gate of Gondor broke. As if stricken by some blasting spell it burst asunder ...
(The Return of the King, Chapter IV, "The Siege of Gondor", p. 810 in my Houghton Mifflin one-volume edition. Emphasis added.)
Why he was called "the Witch-king" may have had more to do with older meanings of the word "witch", and its roots, which come from unclear sources (although Tolkien, who worked on the etymologies of words beginning with "W" for the OED, may have had his own ideas). See here for a good discussion.
Men proved easier to ensnare. Those who used the Nine Rings became mighty in their day, kings, sorcerers, and warriors of old. They obtained glory and great wealth, yet it turned to their undoing. They had, as it seemed, unending life, yet life became unendurable to them. They could walk, if they would, unseen by all eyes in this world beneath the sun, and they could see things in worlds invisible to mortal men; but too often they beheld only the phantoms and delusions of Sauron.
"Of the Rings of Power and the Third Age", published in The Silmarillion
In The Lord of the Rings: A Reader's Companion, Hammond and Scull explain the use of the word "witch" to just mean a person who does magic, not specifically a female.
The use of witch in his title seems odd to contemporary eyes, to whom the word is popularly associated only with females, but its oldest use recorded in the Oxford English Dictionary is ‘a man who practises witchcraft or magic; a magician, sorcerer, wizard’, and for most of its history it belonged to no gender.
The Lord of the Rings: A Reader's Companion - Prologue
As for actual examples of him doing magic, note that flaming lightsaber from the movie actually is in the book. He doesn't break Gandalf's staff though.
The Black Rider flung back his hood, and behold! he had a kingly crown; and yet upon no head visible was it set. The red fires shone between it and the mantled shoulders vast and dark. From a mouth unseen there came a deadly laughter.
‘Old fool!’ he said. ‘Old fool! This is my hour. Do you not know Death when you see it? Die now and curse in vain!’ And with that he lifted high his sword and flames ran down the blade.
The Lord of the Rings - Chapter 4 - "The Siege of Gondor"
Also see Matt Gutting's answer about the gates.
