Allow user to change term, for views and taxonomy
You've done everything right. However, there's a kind of a usability problem with Views, Blocks and Exposed Filters. You can include the exposed filters within the views block by editing the View, then changing "Use AJAX" to yes. Specifically:

Advanced > Other > Use AJAX: Yes