@SlvrYeti @snickers: Have you attempted to make a recording from the trouble channels? It's sounds like you may be running into the issue where the Fire TV Stick 4K cannot hardware decode interlaced H.264 content.
@SlvrYeti, this has been known as a problem, especially for OTA broadcasts in the UK as they often transmit some stations interlaced and H.264 encoded.
@snickers, there are some US cable providers that are also transmitting interlaced H.264 content. The developers have mentioned that this is the case in some Comcast markets; perhaps Verizon/Frontier FiOS markets may be subject to the same problems.
Until Amazon releases the fix for interlaced H.264 hardware decoding, your only real option is to use software decoding.