I'll respectfully disagree with MK. There are many, many patents covering "old" articles made with "new" materials. Just do a quick search in the baseball bat art. There are literally hundreds of patents for baseball bats made with different materials, be they scandium alloys (e.g., SC777), carbon fiber, fiberglass composite, aluminum, etc. Another good example is in the magnetic media art, where there are probably over 20,000 patents drawn to magnetic recording media (e.g., hard discs) having recording layers that are made of different materials.
My experience is that whether or not an old article made with a new material is patentable will depend largely on the novelty and non-obviousness of the new material itself. I.e., small changes in material would likely not be patentable absent secondary considerations, where large material changes might be patentable. With respect to the example postulated by the OP, I would say that we know too little about the synthetic leather to determine whether or not a shoe made of that material would or would not be patentable.
A harder scenario is whether the use of of a known material for a novel use is patentable. E.g., using ground tires for making the running surface of a track and field stadium; using an anti-flu medication to treat cancer; making dental veneers from a ceramic material known for use in pottery glazing, etc. In those instances, it is my experience that patentability turns on the novelty and non-obviousness of the combination of material and use, as opposed to simply the material itself.
Last but certainly not least, it all depends on how the combination is claimed. As MK indicated, it is probably unlikely that claims generally drawn to the use of "synthetic" leather in applications where natural leather was used previously would fly. But claims drawn to a more specific type of synthetic leather could very well be patentable.