Have you considered or changed the Crankshaft position sensor, as another "common" starting issue?
Plus might add, you might want to connect a Code reader to the car to see if there are any specific Errors?