I finally found the root of my problem.
The issue was the SD cards. The first one I had was a 2GB Sandisk I had just bought. Apparently, it is corrupted. I also tried some no name card, and a 1GB Kingston. All gave the same results.
I was digging through my PC crap and found an older 2GB...