I may be completely wrong about this (Do flash drives need the same formatting space as hard drives do? or does the firmware take space included in the 512 megs) but would'nt you need to say something like 500 megs rather than 512?

Here's a good explanation, from ipodlounge.com:

Why don’t I have the full drive capacity I paid for? Using either Windows Explorer or the iTunes capacity bar at the bottom of the iPod shuffle page, you’ll notice that your iPod shuffle is reporting a slightly smaller total hard drive capacity than the number on the box. Don’t worry… this is completely normal for all storage media.
Contrary to popular belief, this anomaly is not caused by factory-installed programs, file system overhead, or swap space… it’s an unfortunate consequence of little more than math and marketing.
Hard drives are sold and marketed using decimal gigabytes. That is, a “GB” consists of 1,000,000,000 bytes. However, computers interpret gigabytes in binary. To a computer, 1 GB = 2^30 bytes, or 1,073,741,824 bytes.
The ratio of “actual” to “marketed” file size is the ratio of these two interpretations, or roughly 0.931.
Therefore, a 512MB iPod shuffle actually has 0.9313225*512MB, or about 476.8MB of space usable to a computer. A 1GB iPod shuffle will similarly report approximately 953.7MB.