Most people have never used voice recognition beyond shouting "Call Dave Jobs[1] Mobile" in the car. This is going to be perceived as magic, in the same way as the accelerometer in the Wii or the original finger touch interface. Anyone with a 4S is going to be showing this off to their friends, and I can't wait to try it.
There are parallels with people saying 'Touch has been around for years, but people prefer buttons' when the iPhone came out. True - until someone did it right. And now everyone wants touch.
And yes, I know it's been around on Android. But Apple make you WANT to use it. No-one's ever been bursting with excitement to show me their Android voice recognition stuff, and nor have I been wetting myself to try it out.
On the downside for Apple - improvements to the iPhone for the foreseeable future look to be on the software/web server side. They are vulnerable here. Limiting features to new models is going to piss people off, and fighting patent battles on software is much, much harder.
[1] Funny typo - I meant to type Dave Jones. Only noticed this on rereading the post.