Problem with extension

Hi everybody, We have a problem with postgres extensions, we have several
servers with several instances on each of them (together 42). Each of those
instances are same (except table names - aplication partitioning). But when
we are preparing to migrate to newer version of Postgres, we discovered
this.
On all servers, there are tables with hstore columns, therefore there is
hstore extension in use. In order to upgrade from 9.3 to 9.5 we need to run
"ALTER EXTENSION hstore UPDATE;" on each database. But on some instances,
it says, there is no extension hstore:

XY=# alter extension hstore update;
ERROR: extension "hstore" does not exist

On "correct" instance \dx shows (after alter):
XY=# \dx
List of installed extensions
Name | Version | Schema | Description
-------------+---------+------------+--------------------------------------------------
adminpack | 1.0 | pg_catalog | administrative functions for
PostgreSQL
hll | 1.0 | public | type for storing hyperloglog data
hstore | 1.2 | public | data type for storing sets of (key,
value) pairs
pgstattuple | 1.0 | public | show tuple-level statistics
plpgsql | 1.0 | pg_catalog | PL/pgSQL procedural language
(5 rows)

On "weird" one \dx shows:
XY=# \dx
List of installed extensions
Name | Version | Schema | Description
-------------+---------+------------+-----------------------------------------
adminpack | 1.0 | pg_catalog | administrative functions for
PostgreSQL
hll | 1.0 | public | type for storing hyperloglog data
pgstattuple | 1.0 | public | show tuple-level statistics
plpgsql | 1.0 | pg_catalog | PL/pgSQL procedural language
(4 rows)

We are running:
Name : postgresql93-server
Arch : x86_64
Version : 9.3.13
Release : 1PGDG.rhel6

On CentOS 6 2.6.32-431.20.3.el6.x86_64
Each instance has a replica on different machine (via WAL shipping as well
as streaming replication) and problem is on both of them (master and slave)

Weird is, when we try to add extension again (via CREATE EXTENSION), it
ends up succesfully, but \dx won't show it

Another thing, when we try to add extesion with insert to pg_extension it
gets OID far greater than any other:
XY=# select *,pg_extension.oid from pg_extension;
extname | extowner | extnamespace | extrelocatable | extversion |
extconfig | extcondition | oid
-------------+----------+--------------+----------------+------------+-----------+--------------+-----------
plpgsql | 10 | 11 | f | 1.0 |
| | 12617
adminpack | 10 | 11 | f | 1.0 |
| | 16471
hll | 10 | 2200 | f | 1.0 |
| | 16472
pgstattuple | 10 | 2200 | t | 1.0 |
| | 16473
hstore | 10 | 2200 | t | 1.2 |
| | 366992783

Any ideas what to do to fix?

Thanks
Tomas