Problem is with X64 version of Windows Server.
The snapin installed via the DVD is for 32bit. A 64bit is however provided to be installed manually from the DVD's folders. I tried it and it still doesn't work - I think it is for IA64, not X64.
I installed the x86 version on another windows 2000 DC and it worked.
I assume it would also work if you install the AD Users and Computers on a wokstation with X86 Windows XP (using adminpak.msi from windows) and then install the x86 snap-in - just in case someone else has same issue.