"choose between cutting significant features from the app or only shipping our new version to the newest Android phones (ICS and up)"
The ICS move wouldn't have been a bad option. It would've helped a lot of users convert to ICS+ devices, which Google probably would've loved.
The APIs from 4+ are much more robust than pre-ICS, and it probably would've saved more headaches while building the new version in addition to the one already described in the post.