Out of shared mem on new box with more mem, 9.1.5 -> 9.1.6

We've run into a perplexing issue with a customer database. He moved
from a 9.1.5 to a 9.1.6 and upgraded from an EC2 m1.medium (3.75GB
RAM, 1.3 GB shmmax), to an m2.xlarge (17GB RAM, 5.7 GB shmmax), and is
now regularly getting constant errors regarding running out of shared
memory (there were none on the old system in the recent couple of
days' logs from before the upgrade):

ERROR:  out of shared memory
HINT:  You might need to increase max_pred_locks_per_transaction.

The query causing this has structurally identical plans on both systems:

old: http://explain.depesz.com/s/Epzq
new: http://explain.depesz.com/s/WZo

The settings ( "select name, setting from pg_settings where source <>
'default' and name not like 'log%' and name not like 'ssl%' and name
not like 'syslog%'" ) are almost identical
(max_pred_locks_per_transaction itself is at the default):

17c17
<  effective_cache_size         | 1530000
---
>  effective_cache_size         | 337500
38c38
<  shared_buffers               | 424960
---
>  shared_buffers               | 93696

The kernels are both 2.6.32. The workload has not changed
significantly. Could something in 9.1.6 be to blame here? Looking at
the changelog, this seems vanishingly unlikely. Any ideas?