PostgreSQL query suddenly very slow after new column addition
It looks like we needed to run ANALYZE users! 

I had run ANALYZE activities, but that wasn't the problematic table. I guess the query planner thought that the api_user_for column would be instructive to help it remove rows, but the column was almost entirely filled with NULL values, so it would not have helped much at all.

Obviously running a simple ANALYZE would also have solved the problem.