Use a flashlight and carefully inspect the CF socket in the camera... look for bent or damaged pins.
Also look very closely at the socket end of the memory cards. Look for any sign of damage.
Hopefully you won't find anything. But if you do, you'll probably need to have the socket repaired.
Other than that, I'd try (some of which have already been suggested):
1. Make sure the camera's firmware is up to date.
2. Format the card in your computer first, then again in the camera before using it.
3. There is a little pin switch on the camera's memory card door. Make sure that's not obstructed. (Note: AFAIK, if that switch weren't working properly the camera wouldn't even power up, so I really don't think this is the problem.)
4. "Reboot" the camera. That might clear something from memory that's causing a problem.
5. Some "recovery" softwares have a built-in card testing and repair applet. I got a copy of such a software some years ago from Lexar, free with the purchase of a card, that works well. It identifies bad sectors on a card and maps around them.
I don't know of any incompatible cards, but it is possible that some older memory cards simply won't work in a newer camera. But the new card you just bought certainly should work. It is possible though, that it's a bad card. Those are rare, but do happen.
I agree with Tzetsin that deleting something like a folder on the card while it's out of the camera might cause a problem. But formating first in the computer, then again in the camera should fix it.
It is good practice to always format the card in-camera, before use. Just be aware that this will erase any and all images already on the card, or allow them to be overwritten. Formatting prepares the card for use, but should be done in-camera so that you are certain it's done properly. Formatting in computer might clear the card, but set up the wrong files structure. It's okay to do that, so long as you remember to format again in-camera before trying to use the card.