Thankfully I found an easy solution to this problem.
When outputting or terms as checkboxes/radios/whatever, we need to change this:
<?php checked( true, is_object_in_term( $user->ID, 'YOUR-TAX', $term ) ); ?>
To this:
<?php checked( true, is_object_in_term( $user->ID, 'YOUR-TAX', $term->term_id ) ); ?>
This is from the function in my original post. YOUR-TAX is where you put in the name of your taxonomy.