useradd is complaining that it cannot allocate a subordinate UID range for the new user because the allowed UID range is exhausted.
As you indicated, you have a lot of users in your system,
and the default values configured in login.defs can't handle that.
Subordinate UID/GID files are used to set up UID/GID mappings for user namespaces (see subuid(5), subgid(5), newuidmap(1), and newgidmap(1) ).
In my case, I had 10000+ UIDs in my system,
and useradd was failing with exactly the same error.
I didn't want useradd to manage the subuid and subgid databases
as I don't need to configure any custom ID mappings,
so I've disabled this feature.
This can be done by removing the /etc/subuid and /etc/subgid files.
For recent versions of shadow utilities (since 4.9 or so),
setting SUB_UID_COUNT 0 and SUB_GID_COUNT 0
in your /etc/login.defs also works.
See login.defs(5) for details.
uname:Linux server 3.19.0-28-lowlatency #30~14.04.1-Ubuntu SMP PREEMPT Tue Sep 1 10:24:39 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux– tildearrow Nov 01 '15 at 17:04/etc/subuidand the highest value was 600016544. – tildearrow Nov 01 '15 at 17:05