Firmware updates don't uninstall with Factory Resets. They're installed to stay. The idea behind it is to erase any cached or working data that is conflicting pre- and post-update. If you made a Samsung Account, make sure to turn on backup/sync for the S-Apps, SMS/MMS, and Call Log.
The fact that it came from China alone makes the device itself suspect, if you're not aware of the cloning. Under About Device, what do the Software Version and Android version say?
Samsung Galaxy S® 4 MJA Rooted with CF Auto-Root Tutorial
HTC EVO Design 4G™ v4.0.3 Bootloader Unlocked & Rooted with HTC SuperTool v3
If it ain't broke, use a sledge hammer.