CF or SD card? What brand?
It sounds like the card, and its cheap to pop a different card in the camera to see if it works. I prefer CF cards, but a reliable brand like Sandisk or Lexar should work fine.
Bad cards are fairly common, so its best to stick with the highest quality ones available. Do not ever buy one from ebay, they are more often counterfit than not.
If you have a different camera, try the card in it.