I had a near similar experience. In iTunes, preferences, you can find a backup. My 3G was disabled and I was able to go back to an older backup which wasn't great but better. My 3Gs had contacts/address book get sideways with lost contacts or contacts broken up. Look for the backup to restore addresses, notes, etc. i0S4.1 is better but not great, best to get off 4.0. If a 3G, some threads point to disabling Spotlight (settings, general, home button) for an increase in speed (works).