It sure sounds like you have an overload of the 20A fuse in the solenoid circuit. It's possible that the solenoid coil is internally shorted and draws more current than it should. Do you know what the resistance of the solenoid coil should be? Measure that with an ohmmeter. Or possibly if the solenoid was designed for 6V, the 12V is making it draw enough more current to blow the fuse.
When you connect the solenoid to the positive battery terminal, is there a fuse in the circuit? If not, and no smoke comes from the solenoid when you do that, you should connect an ammeter in the circuit and see how many amps it draws when you connect to the battery. Dollars to donuts, that's going to be more than 20 amps. But don't just stick a higher amperage fuse in place of the 20 amp one, or you may burn up something more valuable than fuses.
