Actually found a potential way (with WP3.1), but it’s a bit more involved than using filters:
Since WP3.1 now uses the WP_List_Class to generate the admin pages, you can create your own My_User_List_Table class, inheriting from WP_Users_List_Table and in that class override the extra_tablenav() method. In your own method you duplicate the code from WP_Users_List_Table::extra_tablenav() and add your own stuff.
Then you create a duplicate of wp-admin/users.php, modify it to use your class instead and modify the users menu entry in the admin navigation to call your duplicate instead of wp-admin/users.php. I’m not sure if WP3.1 now comes with easier methods to do that then the hacky solutions necessary for WP3.0.
Unfortunately, all this new WP_List_Class stuff comes without good action or filter hooks, it would have been so easy had they added an apply_filters() call to _get_list_table(). Grmpf.