"Discovery Failed" when trying to add devices to Alexa with Sonos One

I get a "Discovery Failed" message when trying to discover devices through my new Sonos One with Alexa. I've followed the following steps:

1. Set up Sonos One and added voice control with Alexa. Alexa responds to commands and knows who I am
2. Set up the Alexa app, connected it to my account
3. Enabled the smart skill for Sonos

I tried both asking Alexas to discover devices ("Alexa, discover devices") and trying to locate devices through the Alexa app but I get a very quick "Discovery Failed" response (see image)

For what it's worth, I've also tried to connect my Nest thermostat by enabling that skill and connecting my account, but that device also cannot be discovered.

Also, I've tried to uninstall my apps and go through this entire process again. That also does not work. Please help.