Have you checked the spark plugs? If they have never been changed it could be not sparking as well as it needs to. I only work on cars but the next place I would check would be the battery as well as the alternator/stator. My Xterra had a cut off issue when it would go above 2k rpm then turn on just fine, I tracked it down to the alternator and have had no problems since. A engine requires air, fuel, and spark to run, it's not air since it starts and runs, you have already addressed the fuel system, just leaves the electrical system not producing a spark.
Good luck!