I've been fortunate that none of my primary accounts were affected. However, since this looks like its fairly common issue, I thought it may be useful to provide some background / translation on what appears to be the dominant issue after upgrading to Mail in Lion for any non-tech types interested.
From what I can tell, most people are having an issues because of a change to the way Mail authenticates with (provides login information to) the mail server. Its important to note, Apple is conforming with the specifications published by a group called the Internet Engineering Task Force. They define Internet standards which all internet software (mail clients, mail servers, web browsers, web servers...) should conform to to ensure interoperability. When any software developer, particularly one as far-reaching as Apple, changes software that interacts with other parties' software or peripherals (in this case Mail servers) the importance of all developers conforming to these standards becomes very apparent.
Since not everyone is having the exact trouble described above, you should try some basic steps before moving on to other workarounds:
+ Confirm the correct mail settings with your provider, including server address, ports, authentication type, encryption requirement, etc. These are typically available on mail provider's websites, but it may require a phone call. Apple has a great resource for collecting mail settings: Configuring Mail for your email account (Mac OS X v10.5 and later).
+ Check your Mail rules to ensure messages are not being redirected to other folders or deleted
+ Disable or uninstall any third party software that integrates with Mail.
+ Check to see if other accounts work, like those from Gmail or Hotmail. If they do and you've already confirmed your account settings, your Mail Provider's mail server probably doesn't like the way Apple Mail is providing login info.
Workarounds / Fixes:
+ Ask your Mail Provider if they support configuring your account to use the IMAP protocol. Some Mail providers allow you to switch depending on your preference. IMAP is actually a more modern standard and typically better if you have multiple devices/clients accessing the same account anyway. You will need to change some settings if this is possible; ask your mail provider for them.
+ Access your Mail using your Email Provider's webmail interface, if one is available (and 99.98% of the time, it will be). An example of this would be rather than checking your Gmail account in Apple Mail, open Safari and login at gmail.com.
+ Forward your account to another free email provider that doesn't have an issue with the way Mail authenticates (Gmail, Hotmail, AOL...). If you want to keep your original account, leave it configured in Mail so you can send from it.
+ Other email clients may still work with your Email Provider. Try Thunderbird or Sparrow.
+ If you're extremely savvy, see the directions knhor provided for changing how authentication works in Apple Mail.
+ After confirming that other accounts work, notify your Mail provider that you're having compatibility issues after upgrading to Apple Mail Version 5.0 in OS X Lion. Ask that they work with Apple to change their software to ensure compatibily.
Hope this helps for people affected by the change! Best of luck to everyone!