The message is telling you that it needs 16.67GB in addition to the 31.38GB that is free, not simply 16.67GB of the 31.38GB. In other words, although there is 31.38GB of free space, you have asked for 48.05GB of media to be added to the phone.
The other thing to take into account is that once you see the message, if you then remove media from the phone (by unticking songs or videos), you then have to click the Sync button in order for the removal of those items to take place. You may have already done this, but I add it as a double-check.
Next: one CD, imported into your iTunes library at 320Kbps (which is good quality) should use up approximately 156MB of space, so nowhere near the the size of the space you currently have on your phone. Even at 1411Kbps in wav format, one album is probably only about 574MB.
It would appear then, that either you are trying to synchronise far more than you think to the phone or there is a lot of Other on it. So let's check.
Connect the phone to your iTunes Library and click on the device icon at the top of the iTunes window (when it appears). At the bottom of each pane (Summary, Music, etc.) look for - and make a note of, the Capacity Bar sizes listed:
On the screenshot above, the amount of Other is so small that you cannot see it. If you hover your mouse over any of the types shown in the Capacity Bar, (Audio, Video, Other, etc.) you will see how much space is being used. There will always be some Other listed, but if it's too large, that's an issue. Usually, a further Sync would reduce it.
If Other is not the problem, you will then have to consider what is being added (or what has been selected for adding to) your phone. For example, if you think that the Video section is too large, perhaps larger than you expect, that's where you should investigate further. What about Podcasts? Do you have any Podcasts synchronised with the phone, in particular, video Podcasts?
Video, in either Podcast form or in the films section, is the largest space hog, so that's what to check first.