My pedals are "new" (6 months and 900 miles) but on my last ride the left one developed an anoying click click every revolution. The mechanic on the century ride said he wasn't surprised, that Shimano pedals will do that. He said he likes Crank Bothers because they have cheap rebuild kits.
I'm useing SPD cleats because I have a difficult time finding shoes that fit and don't want to change now that I've found some comfortable ones.
I thinking I'm justified to return the pedals to REI. Want do you think?