Hmm...I always do new when I get a new device, but now that you mention it, I think I let it do an upgrade. Ugh...do I really have to restore both to new?
Setting up your device as new just prevents future issues, but its not necessary (though a lot of the people who are complaining of battery issues did restore their device from a back-up, I set up as new and my battery is better than before)
But I had a similar issue when I first upgraded to iOS 5 and first of all, just like
HengenJL said, set your caller ID to your email address.
Second, I deleted every conversation from my Messages.app from both my iPhone and my iPad, and I told all of my friends to do the same. From then on all of my conversations stayed in sync.
If this still doesn't fix your syncing issues, try Signing Out of iMessage from Settings> Messages> Sign Out and then just re-sign in (from all of your device).