When viewing the Iteration Status page, the "Add New" button is grayed out with a message stating that "Add New is only available to Editors". The user does have editor permission to the project they are trying to create the new work item in.
Work items can not be added to an iteration that has been accepted so this can be caused when the iteration that is currently selected is in an accepted state.
Change to a different iteration, or open the iteration if it should not be accepted.