Solved!
Not intuitive but I solved the issue.
Within mail, start typing a new message.
Then right click in the message window, go to spelling, and select "Correct Spelling Automatically"
It seems that even if you have "Correct Spelling Automatically" in the Mac System Preferences (under language and text), it doesn't do anything unless you do it again in the message window.
Seems like a bug to me.