Your situation has happened to me twice, each time it was fixed by bleeding. Don't forget the upper bleed on the passenger side.
Of course it could be the booster. When the master cylinder starts leaking (guessing that is why you replaced it) brake fluid can enter the booster, and destroys the seals.