I had the same problem, tried a full restore (as suggested) & didn't help, sadly. Seems to be crashing quite a bit at the moment (even just playing music)
Hopefully 4.1 will help, but I'm not sure that's what the update is aimed at ..
I have the same problem with my 3gs and iOS4.
Apart from the fact that the signal is more unstable now and
i have more dropped calls (even in my home which is 50 m from providers' antenna),
i now have more sluggines interface, applications crash randomly due to low memory,
sound have being lower since then, and i am really pissed from a bug that makes my phone to update carrier settings EVERYTIME i sync it to iTunes.
I even don't want to sync any more, because of this.