if you can start it by linking the 2 terminals, its a wiring problem, simples.
weather or not this is caused by the solenoid getting hot and needing more current to pull it in and the wiring/ circuit components not being able to pass the required current is another matter.