I remember getting the original CotNW (yes the non-Deluxe version) for Christmas one year and had immense fun with the game. Until a few days ago I had no idea that CotNW was still being sold until I created my account on GoG and found this jewel whilst searching for old games (and it's the Deluxe Edition to!) Looks like I'll be spending my weekend either federating Native tribes or declaring my independence from the mother country again thanks to GoG!
If you own the regular edition and are not sure if you should go Deluxe, go Deluxe. One of the features of the D.E is that you can actually read the whole gazette now (thanks to the added arrow buttons and the kind pause until you finish reading), than you could if you had the regular edition. The Deluxe also comes with a scenario editor and if for any reason you need to, you can have the computer take over your turns.
The only minor issue I have is the the intro cinematic is not included. But again it's a minor issue. The rest of the game is great!