Comment 2 for bug 1124250

Have a look into /proc/key-users to see if user root reaches its quotas:

    0: 1029 1028/1028 10/100 2345/20000

means that root uses 1022 from 10000 possible an uses 2345 bytes from maximum 20000.

You may have to encrease both. For each user and group you should increase it by one. So if you 1000 users and 1000 groups you should root allow more than 2000 keys (and enough memory for that).

Try

echo 400000 > /proc/sys/kernel/keys/root_maxbytes
echo 10000 > /proc/sys/kernel/keys/root_maxkeys

and see if this fixes the problem for you.