1.奥様は魔女だったのです。
2.奥様は魔女なのです。
3.東京の大気汚染はひどいのです。
Let me explain the difference if you use の.
な in なの is a variant of copula (です、だ).
の is a nominalizer. (what makes other unit a noun phrase/clause)
In 1, だった is already a copula, so there's no need for nominalizing.
In 2, 魔女 is a noun, and needs a copula.
In 3, ひどい is an adjective, and needs a copula.
EDIT: of course you can say the following, the versions without の.
1.奥様は魔女でした。
2.奥様は魔女です。
3.東京の大気汚染はひどいです。