Got it working! Turns out that you must reset them twice. All of them behaved exactly the same way. To recap:
1) All four bulbs simultaneously stopped working. Other Zigbee plugs and switches continued to work.
2) Normal troubleshooting steps did not work (resetting the Echo, disable/enable devices, multiple new device scans, removing all smart bulbs)
3) The bulbs seemed to respond to the "Reset Philips Hue bulb" command, because they would flash once immediately after sending the reset command, but then they would not be discovered in the following scan. Repeating the discovery scan was also negative.
4) Resetting the bulb a second time causes the bulb to respond to the next scan. In each case, the bulb would flash once after the reset command, and then would flash three times during the scan as they were being discovered by Alexa.
FYI, the Alexa app has been updated, so most of the existing instructions for resetting Philips Hue bulbs are no longer valid. In the current Android version of the Alexa app, 2.2.241878.0, you can find the reset command as follows:
1: Tap the Smart Home icon on the lower right corner of the screen
2: Tap the "+" icon in the top right corner of the screen
3: Select Add Device (this takes you to the SETUP screen)
4: Tap the ? icon on the top right, which takes you to a HELP screen
5: Scroll down to the bottom of the page, tap "here" in the following sentence: "Access pairing instructions for common Zigbee devices here" which takes you to another HELP screen (untitled, connection help?)
6: Scroll down to "RESET PHILIPS HUE LIGHT"
7: Enter the serial number of the bulb to reset
8: Tap Continue, you will see a dialog asking if the light is turned on.
You should see the bulb flash off briefly. Apparently, there is no error message if you do not get the serial number right, so double check the serial number and try again if there is no response at all.
The first time you reset the bulb, the scan will find nothing. At that point you can get back to the connection HELP page with the Hue reset command by tapping the "Get help connecting" button.
Simple, right?
-Jay