Why do iTunes and iPhone not show the same space used?
I had significantly more free memory displayed on the iPhone, while iTunes considered the phone to be full.

Logging out of iCloud and back in again on the phone helped. It is some hassle (at least, I had to reconfigure iCloud and there was some waiting time), but less than the complete reset &amp; restore from backup suggested by others.