Just to confirm something here:
When you turn the ignition ON do you have the red LED for the SKEES antitheft system ON solid?
When turning ignition to Start does the red LED stay ON, engine turns over but does not fire?
If so the problem is as follows:
The SKIM module on top of the steering column sends the key code to the ECM.
The ECM is happy with this code so activated the ASD Relay with ground on one coil pin and +12 volts on the other coil pin. The ECM now expects to get acknowledgement from the ASD Relay that it...the ASD Relay...has activated.
If the ECM does not get this acknowledgement it lights up the red LED solid....not flashing...and lets you turn over the motor but no firing.
You have swapped the ASD relay...no difference!
Remove the ASD relay and inside the empty relay socket jumper female pins 30 and 87 together.
See if it now fires. I had this problem on my 2002. Export CRD whereby the ASD coil was not energizing due to the +12 volts coming off the ignition switch not reaching the one side of the ASD Relay coil due to a break somewhere in the wiring.
I drove around for a while like this until I had time to track down the break in the wiring.!
The KJ Service Manuals are linked in Frequently Asked Questions...section 8W has the wiring diagrams.