I have seen other people with this problem, but their Mail icon was moved out of the applications folder. My Mail is and has always been in the Applications folder, so the problem is not that. I reinstalled the original Mail from the original Snow Leopard installation disk and then installed the system combo update, but it still won't open. I am at the end of my rope!
After an OSX update (10.6.4, 10.6.6, 10.6.8 caused this issue to me) I had the same problem. For the third time in 2 years.
If you're lucky this issue causes one hour wasted to reinstall from DVD, then re-apply patches hoping it will work the first time.
Now if you're tired of this, I have THE definitive solution for you: install thunderbird (which will import your messages even if mail won't open !).
Like with any other operating system it's best to keep operating system and productivity applications from separate providers to minimize risk of something like this happening.
After you move to thunderbird you can move your mail history anywhere, even on windows or linux.
Incidentally, this will also get you a more powerful mail client instead of mail which - besides the upgrade issues - is a really basic client.