Hi Andrew,
I just tried to format an old card and had the same problem as you. This was a fujifilm 128 MB SD card. My regular TwinMOS Ultra-X 1GB has no problems, and my SanDisk 16MB had no problems when the NAVI went to format it.
To format card:
With the unit off, take the card out and make sure the little sliding switch isn't in the "Lock" position on the card.
Put the card back in, and turn the unit on.
Move toggle to the right until "Memory Card" is highlighted, press toggle.
Move toggle down until "Log Switch" is selected, click toggle and select Off.
Move toggle down until "Format Card" is selected, it should say "Fat16", select "Yes" and the card should then be formatted.
To clear data:
Go to Trip Meter, right toggle to "trip max speed", click toggle and select "Zero".
Exit, then right toggle to "Speed". Select "Max Speed", and double click. I usually also go down to select "clear" as well.
Now select "10 s max avg" and double click to reset this.
Right toggle till the display shows your max speed again and you're good to go onto the water!
When sailing:
If you have a good run, click once, go down to "Save", then double click.
Now double click again to reset your displayed max speed.
I usually do this on the return upwind leg, with the NAVI on the left shoulder it's easy to take your right hand off the boom, check your speeds, and do the clicking. One fast gybe at the top of the course later, and I'm zooming back down the run with no stopping

This process allows you to get a reading from each run, and at the end of the day you can see the best max speeds you have achieved by selecting "Restore". I don't use the genie because it's too hard to see what your max speed is when you're bouncing around in the chop.
hth