This most notably happens with iChat. I don't use a firewall, never have on this computer. When I first started using iChat (when Skype 5 came out and sucked hardcore) I couldn't video chat with anyone. It turned out to be the case where my firewall was blocking the necessary connection for video chats. to remedy this I turned the firewall on, put iChat on the "allowed connections list" and then turned the firewall back off (because I don't want the blasted firewall) Well after a completely fresh installation of Mac (don't ask) I forgot to make this same change and ran into a problem where iChat wouldn't even log in. So, remembering the stupidity last time I did the same thing and guess what it works!
So why does the firewall block these connections, particularly from iChat, when the firewall is off? And what does adding iChat to the allowed connections have to do with anything when the firewall is off?