Really? I can boil two cups of water every time, nearly as fast as with an alcohol burner. I use a Ti wing stove, a MSR Titan kettle and a tight-fitting foil windscreen. I've used them for up to 5-day trips on the AT. I've also gotten rolling boils using a canteen stove and cup, and the original Esbit stove with a Sierra cup, as long as I make lids for the cups out of aluminum foil.

Maybe you've got a bad batch of cubes. Did you buy them all at once, or have you tried ones from different purchases?