sensei,
This sounds like some sort of control signal polarity or a power rail problem. Connecting the ByteBlaster will should put a definite value on the nCS, nCE, and nCONFIG signals that might be fixing a polarity problem. Compare you circuitry against the circuit diagram in the Device Handbook.
Otherwise check to see whether the power rails are rising to "recommended operating conditions" within the POR (Power On Reset) timing requirement.
If that fails, you may like to go through Altera's new "Configuration Troubleshooter" to cover all of the basics. Just search on "FPGA Configuration Troubleshooter". Sorry, I can't post links yet.
Regards and good luck,
Mike