My previously checked 34 devices/scenes of probably 70+ were discovered. Here's what worked for me.
(1) Login to Alexa [wound up here: http://alexa.amazon.com/spa/index.html#smart-home
]. (2) Pull the power on my Vera [ie reboot].
(3) I also opened a webpage to my vera at its local ip address on my network.] address to Vera
(4) Then click the new link we got.
(5) Check off or verify checked off devices presented by Vera link.
(6) Click finish and it installs the skill on Alexa, then
(7) under "Your devices" click discover devices. All of mine are found including Nest.
I don't know that my bold items make a difference, but after initial issues this reboot thing seems to help.
I wish the bug hadn't happened, but I do appreciate Vera team getting the patch out so quickly after it was discovered. I don't think my wife even noticed. Thanks.