The issue typically is that the PCM has the wrong VIN (ie. not the original vehicle VIN) - which is different than the other modules attempting communication.
Confirm the PCM is programmed with the correct VIN (this is a separate procedure from flashing a calibration). Once the VIN in the PCM is correct, use the VATS Relink feature - hopefully this gets you going again.
Regards,
Taz