Recently we've changed IP's as we moved servers, and now had an issue sending and recieving e-mail to and from aol and yahoo users. After thinking this new IP set was blacklisted, or at the very least gray listed, i was scratching my head when it came down to the truth because i myself didnt setup the new box, that infact we were not black/gray listed. After some intensive conversations with the PostMaster of aol, we came to this next conclusion;
Make sure your reverse dns is valid, if it isnt, make sure you have a PTR record in your zone files. A reverse dns is needed for some protocols, such as smtp and pop3.
Also it's not a bad idea to apply for a whitelisting with some of these isp's. It also is not a bad idea to add a SPF records to your dns config as well.