l1lvink: Hmm, the version of the game makes sense to me.
I haven't patched the game to the latest version, nor have I added any expansion packs (what I'm using is literally just what came off the disk).
I know that this disk works, as I used it on my previous PC (though this was some years ago).
I would recommend patching it, then. I remember(also, some time ago) having multiple versions of Settlers IV installed at the same time, and even if the game worked fine, the patchless vanilla version wouldn't start(I am speaking of Windows 7 here, which had far less problems running the game than Windows 8), even though the disk worked just fine on older computers.
I also remember getting the exact same error that is being discussed on this topic. :P
So, since the only think I could think of that was different between those versions was the game version, that's what I would suggest doing.
You'll probably have an old version installed, so download both of
these patches. Try running the first one(2.00.1050 to 2.50.1516)first, and then v2.50.1516. Hopefully, and in addition to the rest of fixes present on this topic, you should be able to get your game running!