I had trouble initially but got my Amazon Fire TV 2 working with HA recently. My problem (like yours initially) was that I misread the instructions. I thought there was supposed to be a directory called ‘adbkey’, but it was that the file didn’t have a file extension. So the correct directory to store the files would be in \config\android, or whatever you specified in the configuration.yaml.
Here is the fire tv in my configuration.yaml:
- platform: firetv name: Fire TV host: 192.168.1.111 adbkey: "/config/android/adbkey"
There are two files, ‘adbkey’ and ‘adbkey.pub’. They are stored in the directory \hassio\config\android
Do not store the files in \config\android\adbkey. It should be in \config\android.