I had exactly your situation. I was denied login when I changed my password. I tried logging too many times and they banned me. I contacted yahoo customer service, they replied me and provided me usual answers to get it back using my personal information and secret questions' answers. I had even opportunity to tell them details of my account and contents of my email inside. But that did not help. At last, I tried answering secret questions answers each day (as they banned me for 24 hours after 2 or 3 incorrect entries). In few days I successfully reset the password.
While searching for ways to recover yahoo password, I got suggestions from forum to open a new paid premium account from yahoo. After verifying your information, contact them about your old email account. After verifying they may be able to reset your password. This way at least, they will know you are genuine person. But you should at least provide them the proof that you are the true account holder. But I don't know if it works or not. I just got this suggestion somewhere in the internet but did not have to reach to this point.
If you are in US, it should be bit easier. But just providing them yahoo email address may not help. They are compelled to provide customer service for paid customer. So you may want to think if it is worth trying unless very important information is there at your emails.