One: contact Yahoo as soon as possible to verify that this in fact is the case.
I don´t think this was a "phishing" attempt since it appeared directly on my sign in page not as a separate email from yahoo or whoever.
Two: You could have a bit of malware or spyware on your computer that brought up the very convincing looking message or your have had your browser hijacked to a phishing site that looks exactly like yahoo mail page.
If it is fact an authentic message, perhaps your email address was stolen from one of the many recent high level corporate server hacks that have been publicized recently.
If this is the case, then maybe the password you were previously using was to easy to crack and the person/group who received the subsequent email addresses guessed it or used a simple password cracking program to break into your email address.
Below is an article that might help you and would help prevent further account hacks:
Create strong passwords