Long story short, couldn't get Yahoo! Mail hooked up again on my iPhone, even though it was working in 5.1. I got the "Yahoo! Server Unavailable" when trying to verify the account.
There are a few solutions floating around (delete the iOS Mail account and re-create it, or change your password on Yahoo! and log out/log in to the web site), but the only one that worked for me in iOS 6 was NOT selecting Yahoo! but Other as the account and setting it up manually. Specifically, the servers are:
For the incoming and outgoing mail servers. Working fine now.