Did you dig through every setting on the TV to make sure? It could be buried somewhere weird, or called something unintuitive.
Otherwise, check out this reply thread here, about enabling ADB debugging on the Fire TV and then sending it some commands from a computer to mess with the output resolution: