Users need add/rename file and checkout permissions for the folder that the ECO/ECR form will be placed in. They also need the same permissions for the initial state that the file will be in.
They also need read permissions to the template folder.
Other option is to run the template as a user that does have these permissions. This method forces users to use the template to create the document.
We also had the same issue recently and this was resolved by giving read permissions in our template workflow.
Good luck next team.
Old post but I've just had the same problem with a recently created template. It was caused by the template being checked out - once the template was checked in, users were able to create new docs based on that template.