When your camera formats a card, it doesn't actually check each location on the card to see if it's ok. It just rewites an empty File Allocation Table (FAT) to the card. The SD Card Assocuation has a Formatter
that actually writes to every location on the card. If there's nothing of value on your card now, download the Formatter and use it to format the card. If you've got a counterfiet card, this will tell you.
BTW, when you've sucessfully formatted the card, you'll want to format it again in the camera, so it can create the folders and other things it will expect to see when it writes photos and videos to it.
If all goes well, try it again. It's possible that the Formatter may solve the problem.