I just registered to maybe get you something good to know about the topic. I don't have a MAC notebook or so, but i do have a nootebook PC.
My Sony VAIO does the same things as your mac's does. It recognizes the TV but the TV doesn't recon the notebook. So i just wanted to say to you guys that the problem most likely is the TV as i also have a Samsung LCD-TV (32" LE32S8).
The only way for me to get it working is to connect it up between while having my notebook shut off i can change the TV to PC-input and then start up the notebook and it'll work. But that's the only way for TV to see that it's connected otherwise it won't show me there is a PC-input available.
When i'm connected and using the PC-input, while switcihing over to TV or something else, it will lose the connection to the PC, as the "PC"-input will get greyed out. Very annoying.
So, whatever the problem is, it's must have something to do with the Samsung TV. I know for a fact that samsung had some firmware problems with some of their PC LCD-screens not being recognized correctly either, so this is not the first time it happens to their LCD's.
Anyway, if someone will find an answer for this issue, please post it! I know i will if i do find one.