16 GB is calculated as 1000*1000*1000 bytes by the drive manufacturers.
If you divide that sum by 1024 three times (since computers work in powers of two, not ten), you get an actual capacity of 14.9 GB.
250 MB of space lost to the iPod touch's operating system and assorted databases, etc, sounds about right to me.
I'm not sure about the 13.5 GB turning into 14 when you try to sync it, but I suspect it may either have to do with block sizes or the cover image database.