postgres backup / restore: restored database much smaller?
Maybe it's just index bloat. VACUUM FULL does not help with index bloat, on the contrary, as said in the doc for 8.4:


  The FULL option is not recommended for routine use, but might be
  useful in special cases. An example is when you have deleted or
  updated most of the rows in a table and would like the table to
  physically shrink to occupy less disk space and allow faster table
  scans. VACUUM FULL will usually shrink the table more than a plain
  VACUUM would. The FULL option does not shrink indexes; a periodic
  REINDEX is still recommended. In fact, it is often faster to drop all
  indexes, VACUUM FULL, and recreate the indexes.


(in more recent versions, this advice has disappeared because VACUUM FULL has been reimplemented differently).

See Routine reindeing and the REINDEX command.

The easiest way to reindex is to connect to the database with the db user that owns it and issue:

REINDEX database test_db;


Ideally, it should be done immediately after VACUUM FULL and the database should shrink to its lowest possible size at this point in time.