...warranty indicating they guarantee it works with all phones, then you have a leg to stand on. BBB if CA can walk you through your legal particulars as a consumer. My guess though is, they cover they posterior region by the fine print if you look carefully. Sorry to hear you are having to deal with this- it's a pain to say the least.

There's a whole plethora of complaints about certain handsets not pairing up with specific automobile mfctrs factory equipment, spare all the third party stuff like Kenwood.

A couple of places come to mind where you could check to see if anyone else has a workaround for your system. Edmunds.com and AVSforum.com. Edmunds is probably the premier centralized discussion forum for automobiles/equipment/etc. Howardforums.com sometimes has threads on pairing mobile devices which can come in handy. I didn't see your Kenwood listed, but other folks have had questions regarding the 4S with other stereos, etc.

The closest I have come to anything posted online which deals with your handset/Kenwood in the following from the apple forum. Understand, with each iOS update, quite often features break on external devices.
https://discussions.apple.com/thread/3381837?start=30&tstart=0

hth,
Pedro