It almost sounds like your power brake booster is malfunctioning, giving you a very sensitive pedal and holding itself down. I'm reluctant to suggest this, but one way to test this is to find a big empty parking lot and disconnect the vacuum line to the booster, and plug it on the engine side. Then try your brakes (carefully!-a lot more effort on the brake pedal will be required, so don't be close to anything, and be ready with the emergency brake-it does work, right?). If they don't seem sticky like before, the problem may be the booster. Find out from your mechanic (if you find him) if the power booster was replaced as well. I had one that would put me through the windshield if I looked at it wrong. It didn't hang up or pull itself down but it wasn't too far from doing that. When the car was running and stationary, I could push the pedal almost to the floor with very little effort, which would definitely have locked up the brakes and stood the car on its nose had I been moving. I hate to think of how my rubber brake lines looked when I did this! I replaced the booster and things went back to normal.
If they still feel sticky, then someone may have put the wrong seals in when they rebuilt the master cylinder, causing it to be sticky. This wouldn't explain the oversensitivity though, so my bet is still on the booster.