The new game cinematic is kinda' like that with me too but it freezes with the video every 10 seconds, but a small rectangle in the top left corner will still play... Odd...
I have a 360 and have the same problem, is your TV 60Hz? On the back of the box it says a 60Hz TV is required, i'm not sure if it means for the whole game or just for the cinematics to work. But if it isn't a 60Hz TV I bet that's your problem.