Tokens working for some user roles, not for others

On my site one user role creates most of the content. Some of these pieces of content are edited by a second user role.

I've set up Automatic Node Title, together with Token, so that the nodes should be titled as Node Type [nid]. However, when anyone in the "creator" role first creates a node the node title sets to just "Node Type": it's only when the "editor" role has edited a node that the [nid] bit is bolted on the end.

I've tried to debug this - it must be a permissions issue - but I can't work out the problem. Anyone know what to do?