pw: unable to allocate a new gid - range fully used

How many users are already present?
You've probably used up al available group ids and with every new user, a new group id is needed (for their own group)

The user creation continues and there does not seem to be a problem...  But why is this message appearing, and how do I get rid of it?  There are not many users on the system at all maybe 3-4 users over the base system.

What utility are you using to add users? Is is adduser? And are you adding users as root?

adduser yes and of course as root 8)

Well, I hardly use root, I'm a big fan of sudo. But some things just need root, adduser is not one of them ;P
Anyway, When you add a user, the users Group ID should be within a certain range. Usually this range is between 1000 and 32000 and it's set by min_gid and max_gid.

adduser should be able to retrieve next_gid (which is the next available free gid) and use that for the new users own group. In your case it should be around 1005.

Have a look at your passwd file with
# vipw
and see what groupids are used for your current users.

The last user I created got the GID 1010 so I am even more confused why that message appears...

Looking at the source of pw_group.c I find this:

    330             /*
    331              * Another sanity check
    332              */
    333             if (gid < cnf->min_gid || gid > cnf->max_gid)
    334                   errx(EX_SOFTWARE, "unable to allocate a new gid - range fully used");

In other words you only get the message  if gid is out of range. That doesn't help you any further of course. It just means that min_gid and/or max_gid is not set properly.

If you add a user, what groupid does adduser suggest?

Username: test
Full name:
Uid (Leave empty for default):
pw: unable to allocate a new gid - range fully used
Login group [test]:
Login group is test. Invite test into other groups? []:
Login class [default]:

this is what the output looks like but my guess is 1011 will be the next id given.

Somehow my username had a 30000 GID...  I am guessing that happened in one of the upgrade processes somehow..  Thanks for your help!  The message is gone.

You're welcome :)