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:

com.atlassian.confluence.core.InsufficientPrivilegeException: User [user.name] does not have the required privileges.
    at com.atlassian.confluence.user.DefaultUserAccessor.addMembership(DefaultUserAccessor.java:118)

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:
http://confluence.atlassian.com/display/CONFKB/Unable+to+Create+New+User+Due+to+InsufficientPrivilegeException