You have a whole pile of clues staring at you. First of all, the engine runs when you push-start the car. Forget about the distributor. The engine runs; the distributor has to be working.
"The battery is connected just fine because the lights and beeps all go off, " Do you mean the lights go off when you try to crank the engine? That implies the battery is NOT connected just fine or it is defective. That can be verified with some voltage measurements. I can send you to a web page that shows how to find a bad connection in the starter circuit.
Here's the real big clue: "we can shake the wheel really hard and it will crank". Obviously the starter is working so forget about that as a suspect. Look at what you're affecting by moving the steering column. There may be a rod connecting the key cylinder to the ignition switch, and that switch can be out-of-adjustment or loose. The switch could have an arced contact and pushing on the column moves the switch a little further until a good contact is made. A terminal in the switch connector could be loose or lightly corroded, and moving the column tugs on it enough to make a good contact. You might be tugging on the wires at the clutch switch. There could be a broken wire inside the steering column. All of those things can easily be affected by temperature since metal parts expand when they warm up.
Many Japanese cars don't use a starter relay. That means the ignition switch has to pass the approximately 20 amps to run the starter solenoid instead of the quarter amp to run a relay. That very high current can easily overheat connector terminals and switch contacts. The best way to find the cause of the problem is to take a series of voltage measurements so you know exactly where the bad connection is. You might also try watching underneath while a helper tugs on the steering column, to see what is moving or changing.
The battery is not the cause of the problem. If it was, the engine would still not crank when you tugged on the steering wheel. Since it can be made to crank, you know the battery is okay. The CCA, (cold cranking amps), is a value, not a good or bad. It has to do with the electrical strength designed and built into the battery. That strength does go down with a decrease in temperature, but if that was the cause, the engine wouldn't crank when you push the steering wheel.
Coolant temperature sensor? Who suggested that? That sensor could conceivably make an engine a little harder to start in really cold weather, but the starter will still crank the engine. That sensor has absolutely nothing to do with cranking. You have a simple bad connection. The biggest expense is likely to be for the labor to pay someone to diagnose where it is. The cost of parts could be as little as nothing to as much as a new ignition switch, which isn't that expensive.
Please consider a to help us answer more questions.
Thursday, December 13th, 2012 AT 12:14 AM