I too have had problems with this. But mine was set as secondary, not primary.
I have a Nvida Gforce 4 w/ all the goodies and output options.

I fixed my problem with setting the resolution differently so the tv will understand that format.

It took me some trial and error to get it to work, so I can't tell you the resolution to use.
All of em are different.

I would also recommend getting the latest drivers.