The only thing I can think of other than an obstruction in the release mechanism is something wrong with the springs. Probably best to replace them if that's the case because 1: bad springs make for terrifying crashes and 2: unless you have a quite nice set of pedals, they're cheap to replace.