Would such a person be considered a "natural born citizen," for the
purpose of qualifying for the presidency, from October 25th 1994? In
other words, after having lived in the US for at least 14 years, could
such a person run for the office of the president or the vice
This is an unresolved issue. Some scholars believe that to be a "natural born citizen" you have to be a citizen on the day that you are born. Other scholars believe that a "natural born citizen" is someone who gains citizenship by a means other than naturalization.
No binding precedents resolve the issue because the phrase "natural born citizen" is used nowhere else in the law besides qualification to be the President of the United States, and the issue can't be resolved until someone is purportedly elected because there isn't an actual case or controversy until then, and there haven't been an examples that have come up that have tested this issue.
My personal guess is that the courts would make every effort to find that someone who has been elected by the citizens of the United States as President, despite the inevitable debate by the public over someone's qualification as a "natural born citizen" during the campaign, is eligible to hold that position, because to do otherwise would seem massively undemocratic. So, I suspect that retroactive citizenship at birth would be held by the courts to make someone a "natural born citizen" and eligible to serve as President.
Then again, I could see this issue being resolved by the courts on basically partisan lines too with conservative judges tending to hold that a liberal candidate was ineligible for office, and liberal judges making the opposite conclusions about a liberal candidate. This is one fair reading of what happened in the case of Bush v. Gore.
Would the answer depend on whether the person had been naturalized
The citizenship by naturalization is irrelevant to whether you have another grounds for claiming citizenship that was present at birth or did not arise from naturalization. On October 25th, 1994, the naturalization became redundant.