So the pedal is fully depressed, what does the release handle do? Does it not feel connected? Check that the handle is actuating the release mechanism. Might try spraying some oil in there if it is bound up and tapping it with a soft mallet. Also try pressing the parking brake pedal down slightly while pulling the release, to take the strain off the ratchet pawl.
If it's an emergency you can always cut the cable and reconnect it later. The cable runs along the drivers side framerail.