Posting this in order to help others who, months from now, might Google "OP_WITH_INVALID_USER_TYPE_EXCEPTION" and find this explanation.
We wrote an Apex trigger on the User object, to insert a custom object record anytime a user updates their Chatter status. This was done to fulfill a client's requirement to audit all Chatter activity.
The trigger worked fine, until one day the client signed up some Chatter Free users. When such a user tried to update their status, they got a pop-up with an OP_WITH_INVALID_USER_TYPE_EXCEPTION error.
We scratched our collective heads for awhile. After all, Apex triggers run in "system mode," right? That is supposed to mean that "object and field-level permissions of the current user are ignored." And yet this trigger seemed like it was running in "user mode," enforcing restrictions based on who the current user was.
The root cause turned out to be that a Chatter Free user cannot be the owner of a custom object record, and SFDC by default sets the current user as a new record's first owner. We discovered this when we realized, via experiment, that Apex triggers fired as the result of actions by Chatter Free users could definitely update an existing record, but were having problems creating records.
So the simple solution was to explicitly set the owner of the new record to some fully-licensed user prior to inserting it.