Have you tested the card in a desktop or notebook with USB card reader? This could help determine whether the problem is with the card itself or the Nokia device.

I would also check the write protect switch, although it's been stated here that it's a no-op with these units. (Making a mental note to try that myself next time my N800 is idle.)