A few things come to mind:

1. Is the engine burning oil? Do you see any oil on the plugs? It may need valve work.

2. Was the coil wire swapped out along with the plug wires?

3. The air flow sensor (I forget the correct term, it's in the intake by the fuel distributor, inboard of the circular sensor plate) could be worn out or dirty. Try spraying some air intake cleaner (the stuff for fuel injected engines, not carb engines) up in that area to clean it off. May also want to clean up the electrical contacts/plugs in the engine bay as well.

4. Anything amiss when they run a diagnostic check on the engine?