Someone in another thread pointed me to the following article, which includes information on mail servers for Yahoo's various services:
http://docs.info.apple.com/article.html?artnum=306074
Thing is, the information is out of date. I got e-mail from AT&T Yahoo a couple months ago instructing me to change from smtp.sbcglobal.yahoo.com to smtp.att.yahoo.com. What's more, the old server did not require SSL authentication, and the new server does require SSL authentication.
If Apple's info about server names and protocols is out of date (and it could be out of date for other ISP's too), that could explain a lot. It wouldn't explain why it only happened after the update, though...
(Note also that they list pop.sbcglobal.yahoo.com as the incoming mail server. Not only is that also an out of date, SSL-less server, but it's a POP server, whereas iPhone automatically configures all Yahoo.com accounts to use IMAP. I know nothing about the nuts and bolts of this stuff, but it seems to me that trying to speak IMAP to a POP3 server could also cause weird problems.)