On smaller sized bikes toe overlap is a problem but not common. However toe clip DO have a large cage at the front which would trap newbies not used to it.

Normally most people progress to clippless pedals- ones with there is a cleat on you shoes that locks it to the pedal and by going this way it could remove the toe overlap as there isn't a huge cage hanging off the front.

If you can, remove the toe clips and see if this helps. If it solves it you might want to look into going clipless (which involves buying new pedals and cycle shoes).