Hello, I`m typing from Brazil and I`d like to share my experience about this issue.
First - I think there is no problem with the devices!
Second - The problem, I guess, is in the way we were trying to conect the iPhones to MBsA.
I wasn`t getting a connection between my 3GS and my MBA and the same was going on when I tried with my wife`s and brother`s 4S.
I was at first turnig on Persoanl Hotspot in iPhone then bluetooth in MBA. The devices were paired and then I tried to connect the iPhones to the network and I always got a message when I did that from iPhone saying that the device is not supported or nothing happened when I tried the connection from the MBA. So I changed the way things were being done!
I erased all paring process made before in both devices and did this way:
1 - Turned off Personal Hotspot.
2 - Turned on Bluetooth in iPhone to make it discoverable.
3 - Turned on Bluetooth in MBA.
4 - Paired iPhone and MBA.
5 - Turned on Personal Hotspot.
6 - Clicked on Bluetooth icon in MBA, selected my iPhone and then "Connect to network".
7 - Voilà! The connection was successfuly established!
I did the same thing in the others iPhones and connection in both were successfully established!
Hope I could help all of you!
Ps.: Sorry for any grammar error I could have done.