Check the battery posts for cleanliness and also the connections to the starter, ground, etc. The load of the starter running is dropping the voltage too low to fire the plugs. As soon as the load drops (when you take your foot off the starter pedal), the voltage pops up high enough to fire the ignition system.
