Found the answer to this
$wpdb->insert($wpdb->term_relationships, array("object_id" => $thisMenuItem, "term_taxonomy_id" => $menuID), array("%d", "%d"));
Needed to create the relationship in the database directly. Apparently this is done some where in the saving menu process in the admin. Not sure where, but this did fix it for me.