If you tried to wp_insert_post() with a custom post type, it will not add categories to the post.
The problem is in wp_set_post_categories() in taxonomy.php
In that function, it calls
wp_set_object_terms($post_ID, $post_categories, 'category');
my work around was to create my own function for wp_set_object_terms(). Unfortunately this is not a pluggable function so I had to rename it
chuck_set_object_terms() and call it after wp_insert_post()