I tried to re-create the problem using a SanDisk 8 GB card I keep in my wallet as spare. I couldn't.
I formatted the card on the PC in FAT32. No Canon directory structure as described above. Put it in the camera, took a shot. Voila! Directory structure established, photo saved.
I formatted the card in NTFS! Put it in the camera. Camera says that it doesn't recognize the card, offers to format it. I go for a Low Level format (I always format low level), take a photo and voila! Directories/photo saved.
Since I am running Linux, I formatted the card in ext4 (Linux File System, one of the many). Normally, a drive/card formatted in ext4 would not be detected in a Windows PC. I put in the card in the camera, it said it didn't recognize the card, offered to format it, I accepted, and I took a shot! ...Voila...
Directory structure/photo all there.
I give up! I'd be inclined to say that the mechanical switch which detects the card insertion is broken, but you have two cards that work!
Maybe you could re-flash the camera before you pay Canon?