have you checked your firewall? maybe try to turn it off (sometimes work).

Yeah tried that :(

I have the same problem, but I have been unable to find the cause. It occurs on both 7 and XP. Disabling security software doesn't seem to have any effect.

i had similar problem with carmageddon 3 (i couldn't see anyone even on lan). and i don't know how to make it work;-)

You can play the dosbox version using hamachi.
And if you feel like using command line arguments, you may play eduke32 using hamachi as well (or at least you should, I am about to try it myself):
http://wiki.eduke32.com/wiki/Frequently_Asked_Questions
yep, it works, just tried it out myself.
Just use hamachi with eduke and use windows command line (hope you know how that works). When in the duke directory, use:
eduke32.exe HOST -net -n0:# (#=number of players)
and on the client side:
eduke32.exe JOINING -net -n0 192.168.1.1 (replace Ip with the hamachi IP from your host).
have fun!