I found a workaround:
Install catalyst 9.9
Replace the libaticaldd.so with that of the new driver.
All GPUs are detected.
Correction: See subsequent post. It turns out this workaround worked because it was on a machine that had DISPLAY=:0
I spoke too soon. It turns out fglrx-8.67 works with 4 GPUs:
Then CAL will detect all 4.
It detects only 1 GPU if
NOTE: This is different behaviour than previous CAL releases, but seemingly sensible.