After using the Chrome inspector on the “Appearance > Menus” categories panel I was able to sniff out the hidden form values that are passed when one manually adds a category to a custom menu via the wizard:
<li>
<label class="menu-item-title">
<input type="checkbox" class="menu-item-checkbox" name="menu-item[-11][menu-item-object-id]" value="181"> Category One</label>
<input type="hidden" class="menu-item-db-id" name="menu-item[-11][menu-item-db-id]" value="0">
<input type="hidden" class="menu-item-object" name="menu-item[-11][menu-item-object]" value="category">
<input type="hidden" class="menu-item-parent-id" name="menu-item[-11][menu-item-parent-id]" value="0">
<input type="hidden" class="menu-item-type" name="menu-item[-11][menu-item-type]" value="taxonomy">
<input type="hidden" class="menu-item-title" name="menu-item[-11][menu-item-title]" value="Category One">
<input type="hidden" class="menu-item-url" name="menu-item[-11][menu-item-url]" value="http://localhost:8888/silo4/./category-one/">
<input type="hidden" class="menu-item-target" name="menu-item[-11][menu-item-target]" value="">
<input type="hidden" class="menu-item-attr_title" name="menu-item[-11][menu-item-attr_title]" value="">
<input type="hidden" class="menu-item-classes" name="menu-item[-11][menu-item-classes]" value="">
<input type="hidden" class="menu-item-xfn" name="menu-item[-11][menu-item-xfn]" value="">
</li>
So, the resulting script becomes:
wp_update_nav_menu_item($menu->term_id, 0, array(
'menu-item-title' => $category->name,
'menu-item-object-id' => $category->term_id,
'menu-item-db-id' => 0,
'menu-item-object' => 'category',
'menu-item-parent-id' => 0,
'menu-item-type' => 'taxonomy',
'menu-item-url' => get_category_link($category->term_id),
'menu-item-status' => 'publish',)
);