That's a random sledgehammer, but that is how I have been solving the problem. I've set enable_seqscan, enable_nestloop and enable_material to false and it is working at the moment. At first I only turned off enable_seqscan, but then I turned off the other two after we switched database hosts and the query went belly up.

What scares me is that this is unreliable, and according to the documentation, the optimizer is free to choose to ignore everything that I say whenever it wants. The fact that it already HAS done that to me does not provide me comfort.