Not certain, but this can fix myriad Mail problems...
Safe Boot from the HD, (holding Shift key down at bootup), it will try to repair your Disk Directory while the spinning radian is happening, so let it go, run Disk Utility in Applications>Utilities, then highlight your drive, click on Repair Permissions, then move this folder & file to the Desktop.
Move this Folder to the Desktop...
Move this file to the Desktop...
If that doesn't do it and you can afford to redo all your Rules, try these & reboot...
Note, in 10.5 & up /Users/YourUserName/Library/Caches/Mail/ may or may not exist.
Hello BDAqua: I used your notes to try to repair my macbook pro version 10.6.8. I just noticed the note at the bottom that says it may not exist, and it doesn't. Can you please let me know how I could get my mail icon back? I appreciate your help. Thanks