The 'fast plans' use parallel seq scans. The 'slow plans' is using index scans. It appears a good query plan correctly predicts it should be bulk processing the tables but bad ones get fooled into trashing (hard disk, not SSD) by mispredicting too few rows to join between the tables.
How many tables are involved? Are you sure it is stats getting updated causing the change in behavior? Are you hitting the genetic optimizer?
