No backwards compatibility
I took my iPhone and my bluetooth device in to the Genius Bar and after trying to match them, the genius tried my device with his 3s phone and it worked. Apparently, bluetooth in the 4s is not backwards compatible. I was told that there might be a firmware update to fix this, but I won't be holding my breath.
While I am a Mac user, I also recognize that this is one of those typical frustrations that I have with Apple from time to time. I recently bought a MacMini with Lion and several of my odd music apps no longer work because Lion was updated and no longer supports whatever it is that these apps use. Oh, well, just won't put Lion on my MacPro, until I now longer need those old apps.
While I will say I understand it with Lion, the 4s issue is a little bit odder since I think that compatibility with bluetooth devices for a phone is a safety issue, i.e. if your handsfree doesn't work, then you're not going to use your device handsfree. My advice to Apple, make the fix.