Sounds like a weak battery to me (or a bad connection). When the solenoid engages, voltage drops enough to make it release. If you turn the headlights on while cranking, do they go dim/out? If so, weak battery.