I know this is old but figured I would mention my experience. I saw the same error on my MX-990. Turns out it has something to do with the choice of IR Codes. When I first tried, I picked a random "DVR" type device in the IR Database of the URC software. It wold take it but log the error. But when I tried to reprogram the same key with the same code, it did NOT give that "Already Exists" warning from the FLIRC software. And when I tried to put it into the FireTV, it did not work.
I then tried something more "traditional", namely the Panasonic TV Code 3 set and worked perfectly. No log error, it did give the warning if I tried to use the same IR code in the FLIRC software, and the FireTV responded perfectly.
So not all codes are created equal it seems.
Ernie