It sounds like a wiring or power supply issue to me. Post a photo of your setup and preferably a schematic too, then it will be easier for us to help.
Back emf is generated when the solenoid is switched off rather than on, and can be tamed by connecting a diode in parallel with the solenoid, cathode to positive end, anode to negative end.