How to create new category for custom post type?

You could create a taxonomy called Job Types and your terms would be PHP Jobs etc.

In your register post type function change:

'taxonomies' => array( 'post_tag', "category"),
to

'taxonomies' => array('job_types'),

add_action('init' , 'c3m_job_taxonomis' );
function c3m_job_taxonomies()
  {
     $labels = array(
    'name' => _x( 'Job Types', 'taxonomy general name' ),
    'singular_name' => _x( 'Job Type', 'taxonomy singular name' ),
    'search_items' =>  __( 'Search Job Types' ),
    'all_items' => __( 'All Job Types' ),
    'parent_item' => __( 'Parent Job Types' ),
    'parent_item_colon' => __( 'Parent Job Type:' ),
    'edit_item' => __( 'Edit Job Type' ), 
    'update_item' => __( 'Update Job Type' ),
    'add_new_item' => __( 'Add New Job Type' ),
    'new_item_name' => __( 'New Job Type' ),
  );    

  register_taxonomy('job_type',array('jobs'), array(
    'hierarchical' => true,
    'labels' => $labels,
    'show_ui' => true,
    'query_var' => true,
    'show_in_nav_menus' => true,
     'rewrite' => array('slug' => 'job-types', 'with_front' => false),
  ));   

}