You are right, after a little googling it turns out this is an unresolved bug of Redhat 9. The problem lies in the Shadow-utils RPM, however a fixed version is not available (and it never will since redhat 9 is unsupported).
You could try to upgrade the Shadow program manually, however because many things have changed since redhat 9 was abandoned, it is very possible that something will break.
Of course you can still enter users manually by editing the etc/passwd and etc/shadow files (or automate it with some script).
The only other solution I've found, is install the libuser
program which provides an alternative to useradd (named "luseradd").
if you add user as firstname.last name or FirstNameLastName in Fedora Core4, It allows u to add, but while doing any changes from GUI it gives error "the user name contains puncuation character, Please do not use puncuation in username"