I don't have either of these components so I can't offer any real help, but just as a rule of thumb it is a good idea to wait longer then an hour before posting a help plea. Give people some time to check out the thread.
Does it do the same thing at different settings on the 360? 480p, etc. I am no expert on video game systems, but doesn't the X-Box work like an up-converting DVD player where you could just send the TV 480p and let it do the up-scaling?