That is odd, to say the least. I am guessing here that somehow storage is fragmented and there is not enough contiguous free space.
I would do a "backup, wipe and restore."
In other words, plug your phone into your computer and back it up locally (set a backup password so the backup retains your saved passwords). Once that is done go into settings > general > reset > erase all content and settings, and wipe the phone. Once that is done restore it from the backup you just created.
I have found that this frees up space on an iPhone, presumably removing temporary files and the like and, I am thinking, that it will solve your not enough space error.