So it turns out that the replica-addusers.pl script (https://github.com/wikimedia/operations-puppet/blob/3adbccf1b38a604bba991938d84349da52e7bad2/modules/labstore/files/replica-addusers.pl) responsible for creating user accounts and grants on the labsdb*** boxes depended on many unpuppetized things on labstore1001, among which is a mysql user / password combo that has permissions to create users and do grants - a root account basically.
Unfortunately this wasn't puppetized, and labstore1001 has been completely wiped, so I have no idea which account was being used. Either way, an account that can do nothing but create accounts and give them grants should be created and allowed login from labstore** hosts, and put in the private repository...