Incorrect UsernamePassword for apple.imap.yahoo.com iPhone

Ive been receiving e-mails with few to no problems since I got my phone 2 years ago. Suddenly, I keep getting the error The user name or password for apple.imap.mail.yahoo.com is incorrect. Ive tried deleting the account and re-entering the credentials, reset my phone, powered off the phone, cleared cookies, cache, etc. from Safari, even changed my passwords. Ive read the forums and the responses there-in, but there doesnt seem to be a true solution to this problem. Anyone have a clue how to get around this?
iPhone 3GS iOS 4