Alexa not discovering new devices

I’m using Home Assistant Cloud, and I’ve ensured the entities I’m trying to add are exposed.
I’ve rebooted my HA hardware, disabled and reenabled Alexa integration, synchronized my entities.
Within Alexa, I’ve tried discovering new devices, and disabled and reenabled the skill.
One weird thing I noticed is when I reenabled the skill, I receive a message about Alexa not being able to connect to my device (I’m assuming it means HA Cloud).

Luckily previously added devices still work, I just can’t add new ones.
Any help would be appreciated!