found xmin X from before relfrozenxid Y during vacuum
You might be in luck.

The last but one point release for 9.3 has this change:


  
  Ensure that updates to the relfrozenxid and relminmxid values for "nailed" system catalogs are processed in a timely fashion (Andres Freund)
  
  Overoptimistic caching rules could prevent these updates from being seen by other sessions, leading to spurious errors and/or data corruption. The problem was significantly worse for shared catalogs, such as pg_authid, because the stale cache data could persist into new sessions as well as existing ones.
  


See the discussion on the -hackers list.