Do you have a spare machine you can test on with the new version and a dump of your data? Cache contention seems very likely.
The way to confirm this on the production box would be to turn on statistics gathering in PG (edit the config file/SIGHUP the Postmaster) and to look at cache hit/miss ratios for the relevant tables in your test database.
But better would be to set up on a second machine and do your testing in isolation to remove all doubt. I highly recommend you do this before putting more energy scratching our heads over the query itself.
It may be a good idea to turn on stats on your production box along with testing your test instance on another box (if possible). You may be running on the hairy edge of overloading that server and stats may help determine whether or not more memory should be allocated to the shared buffer, etc.
I have a couple of canned queries available to help make sense of the statistics I can give you if you turn them on and are interested ...
