I just pulled out a fairly full card and the total capacity is 15.06 GB.
THe only thing that could have happened that I can think of is the card was ejected during a recording and has damaged a portion of the memory.
I did this with an SDHC card early on when I didn't realize the recording to the card was actually still happening up to 10 seconds after I pressed the stop button. The card now only has 42 mins available but still works.
Perhaps this has something to do with the term "gigabytes." For instance, a blank DVD comes from the manufacturer with the number "4.7GB" printed on it - but that's using 1,000 as the basis for a kilobyte. Computers, however, use 1,024 as the basis for a kilobyte, and they only get 4.3GB on that DVD disc. Consider that the discrepancy of .4GB is 400MB. Not all of that is due to the base-1000 problem; there are also parts of the disc/card dedicated to directory/TC structure and stuff. If one wanted to multiply by 3.04 (16GB claimed capacity divided by 4.7GB claimed capacity) you're looking at a 1.2GB discrepancy.
That's just my layman's attempt at a possible explanation. I'm just saying it may be a little premature to assume you have a bad card.