OK, I entered a phase where my yahoo login started failing in Pidgin with Ubuntu. I first went in through my.yahoo.com and reactivated my account. It turns out that yahoo turns off your account if you don't login for a few years. =)
After that, it was a problem with the underlying libraries underneath both Pidgin and Adium. On Mac, I updated to the latest version of Adium (1.3.5) and that fixed it.
On ubuntu, it turns out that ubuntu won't update to new versions unless their is a security problem. In order to get functional enhancements, you need to upgrade using pidgin's instructions here:
After you enter those two commands, start update manager and you should be able to upgrade pidgin.