Have you tried asking what the FIOS guy did?
Since the FIOS cable is working and the ones that you have are not and they meet the specifications puzzles me. Maybe the cables are not what they are suppose to be I was thinking possibly a bad HDMI port, but this would not be so if the FIOS guy's cable is working properly and yours are not.
If the FIOS guy's cable is working, I would be curious to know what he says about the cable.
Your TV is set to auto recognize when you plug cables into it, Is the auto feature working properly?
In the TV's setup have you tried doing it manually?
It's also recommended that you turn your TV on first before turning your box on. This allows the HDCP handshake to happen properly.
Do your component inputs work properly?