dc42:
Have you connected a flyback diode across the solenoid yet? The best place to put it is right at the solenoid terminals.
Thanks for the suggestion. I just tried it. It seems to help a bit, but the back EMF is still there as the Arduino gets reset from time to time.