Try re-indexing Mail. open Terminal (/Applications/Utilities/Terminal) and type: sqlite3 ~/Library/Mail/Envelope\ Index vacuum index;
Plus try to throw out Mail Preferences in /YourHardDrive/Users/YourUserName/Library/Preferences/com.apple.mail.plist and see if that helps.