Do you have an LCD TV? I've seen this problem on our Sharp LCD. The problem goes away after the TV has warmed up some. Apparently the backlight caused IR interference (this is a very common problem reported for many STBs, not just the FiOS boxes). When I turned the brightness down some (thus reducing the intensity of the backlight) the problem stopped.
This sounds like the common problem of IR interference. When a TV is first activated, it will draw a lot of power as it warms up, but emit a fair amount of IR in doing so. Some STB/TV combinations are more susceptible than others. Search these forums for "IR interference" for some background and see the solutions implemented. Some TV settings like "vivid" will exacerbate the problem, and changing settings sometimes helps. As a quick confirmation, try this experiment: use a piece of cardboard or similar product to create a "hood" or "visor" to shield the STB from the TV and try the remote. If it responds normally, then you have your answer. Your final solution should, of course, be non-flammable.