How to add post of custom type to a category with custom type capabilities

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.