I'm going to respond to my own question based on what I've learned.
I spoke with Apple about this. The representative indicated that the problem appeared with IOS 5.x. Since my new iPhone 4S has IOS 5.x by default, that is why the phone won't connect to the Audi. I also noticed that my iPhone 3GS, which had been connecting to the car, no longer connected after I upgraded it to IOS 5.0, which supports this theory.
On this surface, this would seem to be an Apple problem. However, it seems that much of the bluetooth software embedded in IOS 5.0 comes from a third party provider. That provider has updated their software to conform to new bluetooth standards, without maintaining backward compatibility. I also have evidence in support of this inference - my wife's Android phone, which is about two years old, also has problems maintaining a reliable bluetooth connection to our 2005 Audi.
It seems like it is the automobile manufacturers' responsibility to update the software in their vehicles to keep it up-to-date with new standards. The dealer that I use says they don't do this, although that might just have been the response of an unknowledgable person. Responses on other threads indicate that people have been able to convince their Audi dealers to update their car's software, with subsequent improvement in performance. According to Audi, cars manufactured in 2010 or later can support the iPhone 4S. I believe this to be true, since my iPhone 4S works flawlessly with my 2010 Q7. This would seem to mean that the software update would have to be to 2010 standards, not the 2007 update which people have mentioned on other threads.
I looked around on these help forums for similar topics, and discovered this one: https://discussions.apple.com/thread/3395922?start=15&tstart=0 "Problems with Bluetooth since IOS 5 upgrade". One solution was suggested on the thread which might be helpful. On my iPhone 4S, I turned off Siri. The phone was then able to pair with the car. I turned Siri back on, and the phone established a connection to the car the next time I got in the car. This morning my wife tried to use the phone. She was unable to make an outgoing call using bluetooth, but was able to receive calls. This was also the behavior of her Android phone.
In conclusion, this seems to be a problem with three causes: 1) Old software in the car, 2) non-backward compatibility of new bluetooth software and 3) some sort of Apple bug caused by Siri. Of the three, I would guess that the Apple bug is the most likely to be fixed, but I don't think that would solve the problem. The most likely way to get this fixed would be for Audi to update their software, and install it in my car. Unfortunately, I don't think that I can hold my breath waiting for that one.
