I have also had this problem. Unfortunately it seems you have to delete everything (or a lot of stuff) already on the USB and then you can sync.
My guess is Rekordbox doesn't calculate the difference in storage between the unsynced/synced files. Like if you have 15GB of total files on your computer - and 10 of those GBs have already been synced to USB, it will still give you an error if you don't have 15GB of free space on your USB. Whereas it really only requires 5GB of extra space. That's just my guess from trying to figure it out myself. Either way, it's a pretty silly bug.