I've got today this issue after I transfered a file from my computer (Ubuntu) to my Nexus One (which runs the stock Android 2.2). After I clicked "Safe Remove Hardware" in Ubuntu, I got the following error on my Nexus One: "SD card damaged. You may have to reformat it". I've searched for more hours on many forums, and it seems that this is more a regular problem for HTC Desire, rather than for the Nexus One (only a few Nexus One users reported this problem).
To be more exactly, this problems seems to be caused by a poor quality of the microSD with which these devices come. I've tried fixing this by rebooting the phone with/without the microSD card inserted, or with apps from the Market, but neither of them worked. I was not at home and I didn't have a (external) card reader with me, so I got stuck there for the moment.
After I got home, it took me some tens of minutes after I got this fixed, so here is what I recommend you doing. Insert the microSD into a card reader, because in this case you have access to what's inside it. Copy all the files on your computer (for backup), and then, using a utility application which can deal with storage drives and partitions, try to completely format the microSD using FAT file system.
I've done it using "Disk Utility", a program which comes preinstalled with Ubuntu. I'm not sure, but the default Windows partitioner should be able to do do the same. I've also tried formatting the microSD directly from the phone but it didn't work.
After you finish formatting the microSD, copy back all your data to it (do not delete your data from the computer yet! keep that for backup), insert it in your phone, power it up, and wait. If everything is fine, the device will start, slowly, to display all data you copied back to the microSD. Music and pictures are going, for example, to be displayed gradually (it may take a few minutes to display all music and pictures). If this happens, you may now delete the data kept for backup in your computer. The only problem is that I don't have anymore all apps I had installed on the microSD. Excepting this, everything is back and working.
If you still have problems or you need help with formatting your microSD, don't hesitate to request help via a comment.