I have found the cause of this problem. The reason is due to the capabilities argument in the category
taxonomy. i.e.
array(
'manage_terms' => 'manage_categories',
'edit_terms' => 'manage_categories',
'delete_terms' => 'manage_categories',
'assign_terms' => 'edit_posts',
);
So one work around (though not a very good one – and certainly not for use in plugins!) is to redefine the Category taxonomy, mapping the ‘assign_terms’ to some other capability (maybe a custom defined one). This capability can then be given to anyone who I want to be able to assign categories. See the Codex page.