Well, it's as simple as "replace maxrun.exe", so it _had_ to work.
Strange then. :/ Either patch is no good, or you have wrong version (you did notice several patches for the different languages, right?), or maybe game is corrupted somewhere before patch.
Well, I see no other ways to help you, unfortunately. My only guess is - maybe try to start the _new_ game and hope for the best? Weak idea, I know.
Hmm, checking local, Abandonia forum, it seems that a) Game maybe is not stuck (5 minutes for opponent's turn recorded) and b) people here used DOS4G 2.01 instead "classic" DOS4GW.
But if you had problems with patch installing, replacing can be not very trivial task...
Ok, here are all possible files:
1.
Modified 1.04 (must give you more memory, but hardly will help with freezing).
2.
Original 1.56 (can be better than 1.04, and the maximum possible version too).
3.
Modified 1.56 (must have more memory).
Download any (or all three) versions and test for yourself.