Seems like the only way to do this is restore my iPhone 4 with a backup from my 3gs. My only question is does both devices have to have the same firmware? Thanks
Nope, you can restore from a previous firmwares backup with your i4.
But I think its a better idea to setup as new instead of restoring from an old 3GS backup IMO.