I've been getting comments about how the workaround given here doesn't work for some particular TV models. Several people have issues with 10.4.9. I would suggest firstly to update to the LATEST (10.4.10 I believe), which is what I've been conducting my tests with.
There is another caveat I failed to mention, and that there is an issue with signal strength that could be at fault. I've read reports on other forums that TVs expect higher signal voltage levels than what the Macbook outputs, resulting in the TV being unable to lock onto the appropriate parts of the signal. This could be the problem for people getting a picture for a moment, and then a garbled nonsense screen. This device could be the answer, although it is pricey. Googling for HDMI ampilfier might help, or if you're and adventuresome electronics tinkerer, you might be able to DIY, that is make a three channel high bandwidth amplifier.
Others have suggested using switchresx:
Take the 1080i settings and just disable interlaced button and set the 30Hz refresh rate to 60Hz. I now get the problem that the picture is totally blurry/blocky. (Thanks David)This is unfortunate, because when this works correctly, you get a glorious full resolution image that looks breathtaking.
My last bit of additional advice is to bootcamp install Windows if all else fails. XP home is sufficient, and hopefully you have an old copy lying around. I retired an old Pentium II machine I had with XP Home on it, and transferred the license/key to my Macbook. Or you can hope Leopard has fixed this issue entirely, but that is a more expensive solution, and one that we have to wait for until next month.