Issue in autovacuum

I had 9.3.0 previously where auto vacuum was working fine where it was able to reclaim space by removing dead tuples.
Version: PostgreSQL 9.4.6 on x86_64-unknown-linux-gnu, compiled by gcc (GCC) 4.4.7 20120313 (Red Hat 4.4.7-16), 64-bit
When I upgrade my db to 9.4.6 (my application remains same and hardly any code change w.r.t transaction declarations), it started complaining about dead rows below. I am not sure if it is something to do with upgrade or not.
One thing, that was happening on my system was there were continuous updates to few tables around 10 million times over a period of 2-3 days.

2017-03-02 19:50:52 GMT [30498]: [41-1] [0] user=,db= LOG: automatic vacuum of table "myschema.mytable": index scans: 0
pages: 0 removed, 23045 remain
tuples: 0 removed, 902169 remain, 900511 are dead but not yet removable
buffer usage: 23060 hits, 26263 misses, 0 dirtied
avg read rate: 2.331 MB/s, avg write rate: 0.000 MB/s
system usage: CPU 0.26s/0.38u sec elapsed 88.02 sec
Not just mytable, even vaccum not able to claim dead rows on postgres internal tables like pg_class

2017-03-02 20:42:02 GMT [15592]: [3-1] [0] user=,db= LOG: automatic vacuum of table "mydb.pg_catalog.pg_class": index scans: 0
pages: 0 removed, 407 remain
tuples: 0 removed, 18876 remain, 16568 are dead but not yet removable
buffer usage: 411 hits, 696 misses, 0 dirtied
avg read rate: 2.424 MB/s, avg write rate: 0.000 MB/s
system usage: CPU 0.00s/0.01u sec elapsed 2.24 sec
CentOS 6.7

My Vacuum configuration:
#------------------------------------------------------------------------------
# AUTOVACUUM PARAMETERS
#------------------------------------------------------------------------------

autovacuum = on # Enable autovacuum subprocess? 'on'
# requires track_counts to also be on.
log_autovacuum_min_duration = 100 # -1 disables, 0 logs all actions and
# their durations, > 0 logs only
# actions running at least this number
# of milliseconds.
#autovacuum_max_workers = 3 # max number of autovacuum subprocesses
# (change requires restart)
#autovacuum_naptime = 1min # time between autovacuum runs
#autovacuum_vacuum_threshold = 50 # min number of row updates before
# vacuum
#autovacuum_analyze_threshold = 50 # min number of row updates before
# analyze
autovacuum_vacuum_scale_factor = 0.05 # fraction of table size before vacuum
autovacuum_analyze_scale_factor = 0.05 # fraction of table size before analyze
#autovacuum_freeze_max_age = 200000000 # maximum XID age before forced vacuum
# (change requires restart)
#autovacuum_vacuum_cost_delay = 20ms # default vacuum cost delay for
# autovacuum, in milliseconds;
# -1 means use vacuum_cost_delay
#autovacuum_vacuum_cost_limit = -1 # default vacuum cost limit for
# autovacuum, -1 means use
# vacuum_cost_limit

Any possible root cause? Is there a known issue in 9.4.6?
Thank you for your time!