Categories for Pages Not Saving in Admin with Custom Categories Metabox?

I’m not sure but I think the simple answer is you have not yet added "noindex" and "nofollow" as categories to your site. Go to the category page in the admin and add them and then I think your code will work, it did for me:

http://example.com/wp-admin/edit-tags.php?taxonomy=category

Of course if you need to add those categories programmatically, ideally for use in a plugin activation so it only ever has to run when the plugin is first activated you can use the following code:

<?php 
/** Include the WordPress Taxonomy Administration API */
require_once(ABSPATH . 'wp-admin/includes/taxonomy.php');
$categories = get_categories('hide_empty=0&fields=names');
if (!in_array('noindex',$categories))
  wp_insert_category(array('cat_name'=>'noindex'));
if (!in_array('nofollow',$categories))
  wp_insert_category(array('cat_name'=>'nofollow'));

UPDATE:

@Scott B: Is it possible that you never associated the category taxonomy with the page post type? You know that Pages (post_type="page") don’t get categories by default, right? Somewhere in your code you need to run register_taxonomy_for_object_type(); my guess is you haven’t?

If I’m right then adding this to your code will almost certainly solve your problem:

add_action('init','attach_category_to_page');
function attach_category_to_page() {
    register_taxonomy_for_object_type('category','page');
}