It appears as though Yahoo has changed something again with their autentication method. We can not authenticate to yahoo via the gateway, but can via direct connect clients such as yahoo messenger and pidgin.
It must have been a temporary issue as it has now gone away. Yahoo is working again.