I had very similar problem when I updated my 3gs from 3.1.3 to 4.0.1, I used rock to rapidly reinstall ALL the tweaks I had on before, this was a fatal mistake, the homescreen was ALWAYS in safe mode, no matter what I did so I was forced to do a restore from scratch, I tried uninstalling many of the things that could be causing this problem but nothing worked, so doing what "iPhone-power" suggested is a good move.