adduser does work as expected, the following warnings are spurious, they just appear when one doesn't have the nscd package. They do not appear on Linux boxes because there posix_spawn doesn't report ENOENT for exec(). POSIX indeed says that `if the error occurs after the calling process successfully returns, the child process shall exit with exit status 127'. The Hurd however reports all errors, thus the warning.

$ sudo adduser foo
Adding user `foo' ...
Adding new group `foo' (1002) ...
posix_spawn() error=1073741826
posix_spawn() error=1073741826
posix_spawn() error=1073741826
Adding new user `foo' (1002) with group `foo' ...
posix_spawn() error=1073741826
posix_spawn() error=1073741826
posix_spawn() error=1073741826
posix_spawn() error=1073741826
Creating home directory `/home/foo' ...
Copying files from `/etc/skel' ...
[...]

Reported at Debian bug #623199.