In addition to allowing ADB connections in developer settings, Android TV and Fire TV
devices usually require individual computers connecting by ADB to "authorize", via a
dialog on the device that appears when you press adbLink's "Connect" button, or manually
connect via the command-line. This is a security setting that insures unknown computers
can't connect to Android without implicit permission.
On your Android TV or Fire TV device screen, look for a pop-up dialog (or full screen) similar to the images below:
For Android TV:
For the Fire TV:
With your remote, confirm the connection and check "Always Allow..."
An authorization "key" is then stored in a .android directory on your PC/Mac in your home directory and in a protected directory on your Android TV or Fire TV device.
If the authorization dialog does not appear, try deleting/renaming the .android/adbkey and .android/adbkey.pub files in your $HOME directory. This should force your device to reauthorize.