結論から言うと、iPhoneとかテザリングで初期設定を終わらせ、その後にWi-Fiを登録すればOK。
なぜか初期設定でWi-Fiの登録に失敗する
Amazon Fire TV Stickを購入して最初の設定時に、ネットワークの設定でWi-Fiを登録しようとすると何度やってもエラーになりました。SSIDやパスワードは正しいのに接続エラーになり、ルーターとAmazon Fire TV Stickを再起動してもWi-Fiを登録できませんでした。
スマホのデザリングで解決
しかし、なぜかiPhoneのテザリングはOKで、テザリングしたまま画面指示に従って初期設定やアップデートまで終わらせた後にネットワークの設定を自宅のWi-Fiを選択したら接続できました。しかも、最初に登録して失敗したはずのSSIDとパスワードを覚えており、それを選択するとサクッと接続できました。意味がわかりません。
同じような症状に遭遇された場合はインターネットにつながっているスマホやタブレットを登録してみてください。