Unlike this previous question, it's not related to iTunes Match (haven't ever had it on).
Why is there such a discrepancy?
Ask Different is a question and answer site for power users of Apple hardware and software. It only takes a minute to sign up.Sign up to join this community
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 & restore from backup suggested by others.