I have tried this in lab (one mho-140 and two SGs, with R81.10 and old T79 jumbo, and it seems that you dont need to reboot all gateways at once. I have started with one SG with non-shared uplinks (two physical ports, bundled in LACP bond), than set shared-uplinks to enabled for this SG, (still alive!), rebooted one of two gateways, than the second, and everything worked fine, without any traffic interruption/link flap. Second SG was than able to use the same uplinks without any problem.
Of course, it was just my lab - your mileage may vary ; -). But it would be nice if Check Point remembered about the poor admins when writing docs, not like "reboot -b all, what's the problem, do you use our hardware for any serious purpose?"