PostgreSQL: pg_upgrade failing because hstore incompatible
So I am having the same problem now that 9.6.1 is out. Here is the only thing I have found so far on-line but haven't tried it out for myself yet. I'll update this answer once I've been able to successful solve the problem.

EDIT: I followed these steps and everything works great. Hopefully when I upgrade to 9.7 it won't be so hard.

Currently on 9.5.4_1

Upgrading to 9.6.1

The answer below is take from this comment with the answer provided by Felix Bünemann. I have modified the steps for my version numbers (see above) and expanded some of the steps with explanations.


  1) While still on [9.5] make sure your hstore databases no longer use the deprecated => operator:

$ for db in `echo 'SELECT datname FROM pg_database;' |/usr/local/Cellar/postgresql/9.5.4_1/bin/psql -t`;do echo $db; echo 'ALTER EXTENSION "hstore" UPDATE;' | /usr/local/Cellar/postgresql/9.5.4_1/bin/psql $db;done



Running this in the terminal basically loops through each of your databases and tries to update the hstore extension for each. See here for more details. There are a few 


  2) stop [9.5] server, brew upgrade postgresql and initdb the new data directory as in the guide


These steps are described in the main article and in my case were already done by this point.


$ launchctl unload ~/Library/LaunchAgents/homebrew.mxcl.postgresql.plist
$ brew update &amp;&amp; brew upgrade postgresql
$ initdb /usr/local/var/postgres9.6 -E utf8


The next 3 steps are to create 3 shell scripts to replace (or wrap) 3 of the programs used in the upgrade process which will be explained later.


  3) Rename [9.6] pg_ctl to pg_ctl.bak and create a shell wrapper as pg_ctl:

#!/bin/sh
ln -sf /usr/local/Cellar/postgresql/9.6.1/lib/postgresql /usr/local/lib/
exec /usr/local/Cellar/postgresql/9.6.1/bin/pg_ctl.bak "$@"

  
  4) Rename [9.6] pg_dump to pg_dump.bak and create a shell wrapper pg_dump:

#!/bin/sh
ln -sf /usr/local/Cellar/postgresql/9.5.4_1/lib/postgresql /usr/local/lib/
exec /usr/local/Cellar/postgresql/9.6.1/bin/pg_dump.bak "$@"

  
  5) Rename [9.6] pg_dumpall to pg_dumpall.bak and create a shell wrapper pg_dumpall:

#!/bin/sh
ln -sf /usr/local/Cellar/postgresql/9.5.4_1/lib/postgresql /usr/local/lib/
exec /usr/local/Cellar/postgresql/9.6.1/bin/pg_dumpall.bak "$@"

  
  6) Make the wrappers executable with chmod +x


$ chmod +x pg_ctl pg_dump pg_dumpall

As stated in a later comment by Felix:


  Essentially what the shell wrappers do is swap around between the [9.6.1] and [9.5.4] lib directories at the right points in the migration process. Because pg_dump needs the [9.5] versions and pg_ctl starts the server which needs the [9.6] ones.


Again remember I am swapping out my versions for everything which you will need to do as well.


  7) Start pg_upgrade as in the guide (this also works with the -k switch, if your low on space, like me)


pg_upgrade -d /usr/local/var/postgres -D /usr/local/var/postgres9.6 -b /usr/local/Cellar/postgresql/9.5.4_1/bin/ -B /usr/local/Cellar/postgresql/9.6.1/bin/ -v



  8) Remove the shell wrappers and rename the .bak files to their original name
  
  9) Swap your data directories as in the guide


$ mv /usr/local/var/postgres /usr/local/var/postgres9.5
$ mv /usr/local/var/postgres9.6 /usr/local/var/postgres



  10) Start the [9.6] server and analyze it using the generated analyze_all.sh script


$ launchctl load ~/Library/LaunchAgents/homebrew.mxcl.postgresql.plist
  # or, if you're running a current version of Homebrew
$ brew services start postgresql



  11) Enjoy postgres 9.6 and grab yourself a coffee for successfully working around the buggy pg_upgrade
  
  Note: If you’re using the pg gem for Rails, you should recompile:

$ gem uninstall pg
$ gem install pg