On my DSM, this usually also happens if I forget to put back one of the ground wires to the chassis. You mentioned the engine block was replaced, you sure everything was hooked back up? From rebuilding my transmission, I know there is a ground right around the pitch stop and another (for the starter) that goes to on one of the bolts to the transmission.
Get that vacuum leak fixed first and do the test to make sure there are no others. I would guess either a ground/electrical issue or a leak.
2007 WRX TR | Stage 2 | PAR Gearset (Built by AndrewTech)