I see your post was several days ago. I hope your problems have been resolved by now. If not, I would call tmo again. When they replace a phone, they send a refurbished one. However, it is my understanding, if they have replaced it 2-3 times (I don't remember how many for sure) they will then replace it with a brand new phone. It sounds like you have just been extremely unlucky with replacements.
And yes, you might try the OS upgrade first. Then if that doesn't work, when you get the replacement phone, make sure it has a current OS before you do much with it.