Before resorting to formatting, which is almost certainly not necessary, try these things:
1. Go to System --> Rockbox Info. Press the select button. Rockbox should scan the disk and recalculate how much free space is available.
2. Check for file system corruption using chkdsk or a similar utility.