You will be happy to know that you're not alone. I also have this issue. Though when I type "me" I get either Mr or Ms 100% of the time and it just blows my mind. I've owned and used every iPhone that has come out and I have never had something so asinine like this happen. It's quite frustrating, particularly because it's "me", it's not something like "anchovy". Like you, I've been trying to "train" my autocorrect stuff for several weeks now and it gets me no where. --sigh--
I have never regretted an apple purchase until iPhone 4. I'm already stuck sitting on the magic fix for the reception issues that will never come. I may as well wait for the fix on this one too.