Why can't I have an Audio conversation using MSN Messenger?

Using NAT, your computer is effectively "hidden" behind your router. For example, each computer will be assigned a private IP or network address that works only behind the router. When that computer then communicates across the internet that Network Address gets Translated to a real, publicly visible internet address. It's safe because from the internet side of the router there's no way to initiate contact with any computers on the private side (unless the router has been explicitly configured to allow certain types of contact).

Unfortunately that means that some communications protocols which try to send the address of computer A behind a NAT router over to computer B somewhere on the internet are destined to fail. They'll send the private address computer A has been assigned, which computer B not being on the private network cannot use.

And so it is with MSN Messenger's Audio (as well as Video and as I understand it, file transfer) protocols. They apparently transmit the IP addresses of both sides of the conversation in ways that NAT routers don't know how to translate. So if there's a NAT anywhere in-between the conversation can't happen.

Microsoft Support has a knowledgebase article that gives essentially the same overview, though their discussion is limitted to Windows 2000 Internet Connection Sharing as the NAT router. (Step one of their "workaround" is to install a proxy server instead, which is no small amount of work.) Whether you're using Windows internet connection sharing or some other type of NAT router the concepts and the resulting problem are the same.

So for now those of us behind NAT routers are safe, but at the cost of not being able to use the audio and video features of Messenger.

It's my understanding though I've not confirmed is that some other instant messaging products such as AOL Instant Messenger (AIM) may use a different protocol and hence may not be affected by this issue.

You can learn much more about NAT here.