Not all devices will accept a transition mode WPA2/3, especially IoT devices.
I suggest you try to circumvent the most obvious issue and try another SSID with WPA2 only and see if it connects there.
If you have wireless capture tool you could try to see what your device does, but usually in this case you'll see the client not even bothering to send an auth request frame because it did not like what was in the probe response.
If that helps then you could check for the Firestick support if there is a software version that fixes this.
Edit: I didn't notice your problem went away after rebooting the MR.
But does it keep working? Maybe disconnect your TV first and try re-connecting.