I have only had my phone for about a week and the hdmi out works fine on mine. There are a lot of different unknowns in this situation and its hard to tell which one it is. It could be the movie, the HDMI cable, the TV, or the app that you are using to play the movie. I use a $14 cable I bought from wal-mart.
At the Verizon store they had the RHD(demo) hooked up to a 40 inch Samsung flat screen and it looked horrible. Even the home screens looked grainy. They also had the phone hooked up to the usb charger at the same time. I have never used both hdmi and usb at the same time so this could be an issue.( I would test it right now but I'm at work)
Hope this helps.