nalin, is there a way that libuser could tell us what the lowest unallocated uid
and gid is?

Changing component to libuser since it is what decides what UID to allocate to a
new user and group.

The lowest unallocated uid/gid is available as
ADMIN.getFirstUnused{Uid,Gid}.

When creating an user, s-c-users currently:
* creates an user entity
  This also calls lu_user_default (), filling the entity with
  a default (first unallocated) UID and GID and interpreting the
  config file, which by default sets GID == UID [without checking
  whether the GID already exists and without making sure the
  group gets created, but that's another story]
* modifies the user entity, including setting the UID manually,
  if needed
* if a private group is desired:
  - creates a group entity
    This calls lu_group_default(), filling a default GID
  - sets user->GID = group->GID
  - creates the group
* creates the user

I can't see any reasonable place where libuser would cause the GID
to be equal to UID.

s-c-users, OTOH, has the following possibilities:
* check whether "UID" is a free GID value, and set it in the
  group entity manually if it is free
* use the GID from user entity, check whether it is a free GID value,
  and set it in the group entity if it is free
  (this depends on the default libuser config which specifies
  userdefaults/LU_GIDNUMBER = %u).

system-config-users-1.2.19-1 should have a fix for this.