Well it seems upgrading firmware and etc is usually recommended with Rest Factory Settings. Google did pretty well on backing up my downloaded apps and contact database (merged with google). Kies did well on my settings, note and also sms and photos.
However, I think they are not the best backup tools here as I do face careless problem like e.g. lost of game save data e.g. PSX Emulator, outdated whatsapp backup (Although I swear I hitted backup before Reset.)
So what kind of Backup App you all used and recommended? I heard about Titanium Backup. However my phone is not rooted. :/