Is the pedal soft or hard when you push on it? That is, does the hydraulic system seem ok? Will the car move if you try to push it? Maybe if the car sat a while there is some light rust on rotors and other parts (or if it is really cold, ice). You could try to break each wheel free with some light impact on wheel, rotor, etc. It's certainly not rare to have parking brake mechanisms bind or freeze, especially if not used much and in cold weather, even on cars that are being driven daily.