There is a dispute in the Gemara in Yoma and Yevamos what is the definition of a shoe. The Shulchan Aruch paskens in Siman תרי"ד that only leather (or leather covered) shoes are prohibited on Yom Kippur. However the Mishan Berura there writes that טוב להחמיר not to wear non-leather shoes.
R' Shternbuch (Moadim U'Zmanim 6:28) writes that today this chumra of the MB may be מעיקר הדין. He makes the following 2 points.
1. Today non-leather shoes/sneakers are as comfortable or more comfortable then leather shoes. The Rambam writes that the reason why non-leather shoes are permitted is because שהרי קושי הארץ מגיע לרגליו, ומרגיש שהוא יחף he feels the hard ground and he feels like he is barefoot, nowadays this no longer applies.
2. Non leather shoes/sneakers are worn outside the house as shoes. This may give them the status of shoes since they have the shape of a shoe.
R' Shternbuch recommends wearing house slippers or wearing just socks to get around this problem.
The minhag seems to be to be מיקל (and R' Shternbuch hinself says יש על מה לסמוך and you shouldn't be look askance at anyone who is מיקל and wears non-leather shoes) however, IMHO, on Yom Kippur, the holiest day of the year, where we are asking for mechila and kappara for our sins, it would not be a bad idea to be machmir here on something that is relatively easy to do.