I remember reading somewhere that it was best to do a update and Restore as new when Updating iPhone OS I did the 4.1 to 4.2 Update yesterday on my iPhone 3GS and I don't remember getting the option to restore as new at the end. I didn't use it much after I did this update but I noticed the battery life was a little better, but also noticed that things are not as snappy/quick, Like launching apps and internet. It did help turning off then turning on my iPhone. I may give it a day or so and restore it.
I always restore and set it up as new. That way I'm sure I have the best performance in the iOS.
This what I also do just tryed it differently this time. I may do a restore on it, I know I was at an Apple Store a while back and overheard a Tech say this to somebody also.