Well, I looked a bit at CPAN. There was another YIM module, Net::YMSG
which appeared to be incredibly similar to the Net::YahooMessenger which you found. It appears to be languishing a bit, and it seems to me there have been protocol changes in the last couple years. The problem might not be your code?
It's not what you asked for, but have you considered Jabber instead? It is an open protocol with both client and server code available in Perl. You could look at Net::Jabber::Client for client code, or check out the big picture at jabber.org
good luck! --bibo