Check the caliper slides and pins. A frozen or bent pin can give a mushy pedal.

does the pedal sink to the floor?