Do you have a firewall blocking Yahoo! Voice? If so, you need to open up some outgoing TCP connections. Note that it is the outgoing connections that matter, not incoming connections. In most firewalls, you have to specify a destination port or port range to open. Yahoo! Messenger uses ports 5050, or 443, or 80.

Even if you don't use a firewall, your Internet service provider (ISP) might use a firewall, a network address translator (NAT), or a proxy server that blocks voice traffic. Any of these could prevent you from using the PC-to-PC voice feature in Yahoo! Messenger. Please contact your ISP's network administrator for assistance getting around these issues.