I thought I’d add my experience of setting up Alexa on a Samsung Android phone with a second generation Echo. I followed the setup procedure as guided by the Alexa app but got stuck at the point where you switch to the phone's settings for wifi and select the network named AmazonXXX (where X can be anything). When I chose this it would say "Connected, no internet" and I assumed there was a problem. You will find advice on the web about this issue which only adds to the confusion here. For example a site named guidingtech.com states “Once you connect to this Amazon Wi-Fi, you'll get a notification saying Wi-Fi has no Internet access on Android. Tap the notification and select Yes from the pop-up menu.”
After hours of fruitless head scratching, rebooting of the router etc. I decided to ignore the fact that the special Amazon wifi was showing as connected but with
no internet (whatever that means!) and just clicked on “continue” in the Alexa app. I then was able to carry on with the setup process including connecting my Echo to my real wi-fi name (SSID) by entering the wifi password into the Alexa app.
So ignore advice to tap on the warning box and click on yes! At least this worked for me. Good luck!