Security permissions for complete require the user to have the ability to change status, the ability to complete work, and the ability to initiate the work order (if it is not already in an INPRG status). A lot of people forget to grant the initiate permission so I would make sure that it's granted.
Beyond that, it could be configuration in your environment such as conditions on the domain values. Some customers like to hide COMP unless some criteria is met (such as a labor transaction is entered). I hate using conditions on domains because it's not clear to the user what they need to do to fix the issue which is a frustrating user experience. You can check if you have conditions on the domain values by going to the Domains application, opening the WOSTATUS domain, and then for the COMP value(s) using the View/Modify Conditions to see conditions that have been tied to the domain value.
You mentioned workflow and there is a process in workflow to prevent status changes outside of the workflow. However, you should receive a different error message in that scenario which is why I didn't go down that path.
------------------------------
Steven Shull
Naviam
------------------------------