Maxim,
I have been playing with the ciphers as well, and it doesn't appear to be cipher related. It happens for every cipher I've tried. I tried with turning off the prefer on the server, and it uses the same cipher with the prefer on. I then turned prefer server ciphers back on, and tailed our access logs which show which cipher was used for the communication. I then went through cipher by cipher, disabled the cipher in our config and restarted nginx each time. None of them had any difference, we're still seeing lots of fallbacks exclusively from our iOS clients.

I tried the following ciphers to no avail:

ECDHE-RSA-AES256-SHA384
ECDHE-RSA-AES128-SHA256
ECDHE-RSA-AES256-SHA
ECDHE-RSA-AES128-SHA
DHE-RSA-AES256-SHA256
DHE-RSA-AES256-SHA
DHE-RSA-AES128-SHA256
DHE-RSA-AES128-SHA