First off, try your resolution change. Put it in 640x480 or 800x600 because everything supports them. :)
If that doesn't work, is it possible to use DVI or HDMI to hook them up? VGA is an brown townog cable, DVI and HDMI are digital and better at compatibility.
If say your TV has an HDMI in, and your Laptop has a DVI out, you could try using a converter cable or just a converter gadget at one end, so the signal is digital.