Had the same problem, except my Samsung Tablet Android version is 5.0.2. What I found is that the Alexa App is not compatible with all versions of Android OS, even if it is 5 and above. So, after trying to get help from Amazon, which did not go well, I decided to go back to the version that was running on my Tablet before I tried upgrading. I searched for the old version of the apk and found:
https://www.apkmonk.com/app/com.amazon.dee.app/This place has all the versions. I tried the newest with the same results. I worked back until I found one that worked.
The one that worked for my tab was the Oct 25 2017. I downloaded and saved that copy, in case I run into this problem again after an update, I will have a baseline.
Hope this helps. Good Luck.