Your logic is not correct. For a while, there were people offering unlocking services for around US$170 who are believed to have bribed an employee of Apple or a mobile phone operator to unlock phones using the official channels, and those phones also didn't need to be jailbroken. There's no way I know of to distinguish one of those phones from a factory unlocked one.
Assuming it is a genuine factory unlock, there should be no problems -- I have a UK factory unlocked iPhone 4 and have upgraded the OS several times, though I've never tried to do so in another country.
I'm inclined to think something has corrupted your preference files or application data, as those will be brought back after a restore from backup.
In order to test this theory, you will need to wipe the phone by putting it in DFU mode, then restoring to the latest Apple firmware through iTunes. Then set up your device as a new device. If the problems still occur (unlikely), then I would take it in to an Apple Store and have a Genius look at it.
If, however, it fixes the issue, then you will have to play "hunt and go seek" with the culprit. Restore your backup, jailbreak (but don't install anything from Cydia except OpenSSH so you can access the file system), and root through your "home" folder (/private/var/mobile).
You should try deleting the preferences (plists) first (~/Library/Preferences), then rebooting. Don't worry, iOS will recreate them. If that doesn't fix it, try removing the sqlite database in ~/Library/Twitter, although I have a feeling the preference files should take care of it.
I wish I had an easy answer for you, but it's going to take some study of the file system and tracing back to the package that "infected" your system.
Not everything in Cydia is deemed safe and you may wish to exercise more caution in the future. MobileSubstrate (which is only made possible be reverse engineering) provides the hooks for many deep level APIs that shouldn't be messed with.
Additionally, you may want to hit up jailbreakqa for additional help, as that is the official forum for help on these matters. From my experience, there isn't much help here regarding this process.
Best Answer
You don't - without SHSH2 blobs you won't be able to.