Actually DD while 2e did not have this particular problem. But I would second MumOfThree's suggestion--apparently this is also common in e.g., Germany--kids there often learn to ride on bikes without pedals, so they get the balancing part first (and move by kicking along on either side of the bike). Of course this works much better in an area without hills, but anyway. Then when they get the balancing part down, you add the pedals. There was also something on NPR recently about a bike lesson for grownups in D.C. who had never learned to ride using the same technique to get going very quickly. Do you think something like that would help? But you said he had learned how to pedal--do you think maybe his bigger bike is too big or too heavy for him to manage easily? Maybe a bike on the small side would be easier for him.
