So if you press the Power button to shut the phone off, then long-press the Power Off option in the menu that comes up, you don't get a Safe Mode prompt, as described in the above link?
If the factory reset doesn't clear things up, then it might be a firmware issue, since Safe Mode essentially eliminates problems caused by 3rd party apps.