Right, URE’s edit restrictions add-on works this way by design. I have a strong reason for this behavior, not one expected by you.
When you input category ID to the user profile such user is allowed to edit just post with that category ID. When user adds new post WordPress added a new post record and then re-open it for editing as the existing post. If this post will not have at least one category from the list of allowed for this user, user will not can to proceed with new added post due to edit restrictions applied to him.
URE assigns to the new added post the 1st category from the list of allowed categories automatically exactly for the reason described above.
