It sure sounds like your talking about the ecu. However, if you look directly on the opposite side of the ecu the fuel pump relay is right there. You might try checking that out if you already haven't done that.(I know you said you replaced a relay, but which one?) I know I had the same exact problem when i first got swapped over to a five speed. I couldn't figure out why the car wouldn't start and why the fuel pump wasn't working. It was cause I only had the tcu (didn't need) plugged in instead of the ecu.
And one other time I was driving home and the 87 octane code from LAN's chip managed to come loose and hang down. Needless to say I ended up pulling the chip out and lost everything on the spot. I had to pull the ecu out right before charley came through...Either way sorry about the rant, just bored....