You can use wp_set_object_terms
after the post is saved and in case it fails you will get reason for that ex:
$new_lead = array(
'post_title' => $lead_name,
'post_content' => $lead_message,
'post_type' => 'leads',
'post_status' => 'publish',
);
$lid = wp_insert_post($new_lead);
$status = wp_set_object_terms($lid,$term_id,'lead-status');
Now this does the save but $status will hold the reason for failure in a failed case.