Rhodiumtoad on IRC helped me figure out how to move part of the query into a CTE in order to work around the planner problem. This is a hack but it brings the time down from many hours to 17 seconds, which is better than it was even with the better plan in the first place! For some reason it actually gets 2 seconds faster yet by putting it in a SQL function rather than using prepare/execute.
Hopefully some improvements to the planner can come from this information?