I have a cheap ebay SD card built by LC Technology http://www.lctech-inc.com the module has a 2x8 block-header, and I'm using a 32G SanDisk SDHC. I used the sdcard.org v4 formatter to ensure it's filesystem is optimised.
The problem is, it fails to initialize on boot. Pressing the reset button on the Arduino (Duemillanove) makes no difference, but ejecting and reinserting the SD card allows the card to successfully initialize once. But hitting reset again then fails again to initialize.
I've tried the example sketches, and the end result is as I've described above.
I will add, when I very first got the module it was working every time; using the example sketches, and I don't recall anything significant enough to cause the problem I'm now experiencing.