I've had the same issue, to an extent. If I use the default app for messaging, all of my incoming texts are stamped as eastern time, and mine are central. So the thread is messed up. I'm in Central Timezone btw.
That said, I was in Orlando last week (Eastern time) and everything was fine with both incoming and outgoing. And to top it all off, if I use Handcent, everything is fine here at home, too.
Weird quirks, and annoying. I know the "easy" answer is to use Handcent, but why is the app that ships with phone dorked?