What size is the frame and what size wheels did they put on the bike? Some really small frames use 650c wheels instead of 700c wheels to help with the toe overlap problem.

Even my bike (53 cm frame) has some toe overlap, but it's only a problem at really low speeds and I've learned to be careful.

The bike shop really should help you with both issues since it is a brand new bike.