Did you install TinyUmbrella in your computer, or have your hosts file points to the Cydia installed of Apple? If so, make sure you change that back before the restore. Otherwise, it won't update the modem baseband, and they can tell it's jailbroken.