The addMembership method returns the InsufficientPrivilegeException when the group does not exist, even when the user has sufficient permissions to add a user to a group. Additionally, if the "confluence-users" group does not exist or the "users" group in Confluence only OnDemand, this error can occur when trying to create a new user in Confluence.
The exception thrown suggests a permissions problem:
However this exception is wrong/misleading, and does not reflect the true cause of failure, which is that the group does not exist.
On a side note, we have KB article on this, but I didn't find a bug filed for it: