Incidentally, for anyone still looking for this, the way I found to do it is to use wp_query's tax_query object (a WP_Tax_Query) to generate SQL that you can then use against arbitrary objects, like Users.
I'm using the Query Multiple Taxonomies plugin to generate my taxonomy queries, but I think this should work with any taxonomy query. Example code from my taxonomy.php to grab all user_ids for users matching the current taxonomy query:
extract($wp_query->tax_query->get_sql( $wpdb->users, 'ID' ));
$user_ids = $wpdb->get_col( "SELECT $wpdb->users.ID FROM $wpdb->users $join WHERE 1=1 $where" );
At this point, you could, of course, grab anything you liked from the users table, etc., by altering this query, or, more clumsily, I suppose, just call get_userdata() or whatever on each of the user_ids you get back.
(This method was partly inspired by the tax_query snippet found here: http://wordpress.stackexchange.com/questions/16393/show-certain-terms-from-custom-taxonomy-but-exclude-parent-terms/16795#16795 )