Two things: 1) /usr/lib/games/nethack/nethack should be chmod-ed 2755, owned by root and belonging to group games. I suspect this is where your problem lies. /usr/games/nethack is just a wrapper shell script to execute the nethack binary.
2) Are you running hamm (Debian 2.0) or slink (frozen)? I'm running frozen and the latest version of the nethack package is 3.2.2-15. Hope that helps, Alan