Switch between iPhone 4 and iPhone 4S
Back up both phones in iTunes. You can do this on separate computers to avoid confusion.
Factory reset both iPhones.
Insert the new SIMs in the phones.
Restore the phones from the backups you made in step 1. Specifically, restore the 4S from the 4's backup and the 4 from the 3G's backup.


If it doesn't work out you can just restore your phone from the latest backup.