Welcome to trying to send e-mail to yahoo.
In the past when I have built new mail servers, the IP addresses have always been blocked.
I don't know if I'm just unlucky that the previous server renter was a spammer or what the case is...
If you look at your mail server logs, you should have an exact error code and message you received from Yahoo.
Anyways, check out this page.
http://help.yahoo.com/l/us/yahoo/mail/post...PgZtWjRmh0lJHdGOn that page, there is a form for bulk mailers to explan themselves or a form for regular mail server admins.
Fill out the form with great detail and provide honest answers.
Let me warn you, this won't be a fast process. Once you fill out the form, they will keep sending you other forms and questions you will also need to fill out to the e-mail address you provide.
This process has taken me two to three weeks in the past.
Also, you will want to do what eth00 has said with SPF, domainkeys, etc.