A bad check valve would give you a hard pedal, with no power assist. Try pressing the pedal a couple of times with the car turned off. I bet it will be more difficult to press to the floor even if you have air in the MC or lines.
Look for a leaking calipar or rear brake cyl. If these leak fluid, it would account for a soft pedal as well.
Bleed the brakes again as granitestategn suggests. Both the MC/Bench and all 4 bleeder screws.
I recommend getting those expencive "HELP!" bleeder screws! Man, those things kick ass! Just open them a little, attach a hose to the bleeder screw, run it to a can, and pump away! They have a check valve in them, so air never finds its way in.