Query plan changes after pg_dump / pg_restore

Greetings all,
I am continously encountering an issue with query plans that changes after
a pg_dump / pg_restore operation has been performed.
On the production database, PostGre refuses to use the defined indexes in
several queries however once the database has been dumped and restored
either on another server or on the same database server it suddenly
"magically" changes the query plan to utilize the indexes thereby cutting
the query cost down to 10% of the original.
Databases are running on the same PostGre v7.3.9 on RH Enterprise 3.1
server.

A VACUUM FULL runs regularly once a day and VACUUM ANALYZE every other
hour.
The data in the tables affected by this query doesn't change very often
Even doing a manual VACUUM FULL, VACUUM ANALYZE or REINDEX before the
query is run on the production database changes nothing.
Have tried to drop the indexes completely and re-create them as well, all
to no avail.

If the queries are run with SET ENABLE_SEQSCAN TO OFF, the live database
uses the correct indexes as expected.

Have placed an export of the query, query plan etc. online at:
http://213.173.234.215:8080/plan.htm in order to ensure it's still
readable.
For the plans, the key tables are marked with bold.

Any insight into why PostGre behaves this way as well as a possible
solution (other than performing a pg_dump / pg_restore on the live
database) would be very much appreciated?

Cheers
Jona