From a philosophical perspective, the mere fact that the question can be asked already indicates that it is NOT the same (in the ship or teleportation case), since such a question is meaningless when only an original is considered.

There is certainly a "sameness" about it, just as one would have with a copy, but it isn't the same.  For example, if we considered using the new ship, we might find that it is more seaworthy, or leakier, or whatever.  In noting such a characteristic we would be forced to consider that whatever its behavior, it could be due to the fact that it was no longer the same ship used originally.

One of the quotes indicates that newer and stronger wood was used, but why stop there?  Why not use steel when it becomes possible?  or fiberglass?  The point is that the similarity between the "new" and the "original" is being superficially maintained but they are not and cannot be the same vessel.

In particular, the "samenss" being attributed to the vessel is an attempt to freeze it in time to commemorate a particular event.  However, it is useful to consider what it would mean if Theseus had kept the ship and maintained it himself.  Would the improvements, repairs, and evolution of the ship constitute the same vessel some years later?  In truth, it would be more Theseus' ship than the maintained copy, but in both cases, it would not be the ship originally employed.

The question is also raised about what creates identity, but this is also a misleading question because it isn't identity, but rather "identical" which is being questioned.  There's no question we can all recognize a human hand, but it would hardly be reasonable to say that they are not fundamentally identical.   We can also see differences, but they are not significant enough to cause identity problems.  In the same vein, one has to consider that the changes in the wood for the ship represent the same kind of changes which allows us to identify a hand and yet recognize that they are not all the same.

Consider whether Theseus's ship would still be significant if it was a myth that it had ever been used?  Which would have a more profound effect?  The changing materials, or the story that accompanied it?

I'm with Gerhard on this - it isn't the same ship. The very use of the word "new" and "stronger" implies different. In Book X of Plato's Republic, Socrates and Glaucon address imitation in a similar vein:

Now do you suppose that if a person were able to make the original as well as the image, he would seriously devote himself to the image-making branch? Would he allow imitation to be the ruling principle of his life, as if he had nothing higher in him?

I should say not.

The real artist, who knew what he was imitating, would be interested in realities and not in imitations; and would desire to leave as memorials of himself works many and fair; and, instead of being the author of encomiums, he would prefer to be the theme of them.

I like that idea - that while Theseus' ship had been updated and was not the same as the original, the ship was still "his" in theme, myth, legend, idea.

Here's another question: in the situation Nuno Cravino described in which a person is replicated exactly, would the copy necessarily make the same decisions as the original? Would the two, given the exact same circumstances, act the same?

A thought - what if there was only one 'person', be it the original or the copy? Nuno writes, "So if I were teleported in a way that my 'original' molecules were destroyed would I die or would I be alive in the copy? What if the molecules were copied and the original not destroyed who of the two would be really myself?"

In the second instance I'd agree with Gerhard, if there was knowledge of the copy, and Hank in either case. As for the first - if there is only one, wouldn't that one have all of the memories, the molecules, the essence? It wouldn't make a difference, then, unlike the ship, which had new parts replacing the old. This reminds me of The Prestige, in which Robert Angier (Hugh Jackman) harnesses the genius of Nikola Tesla (David Bowie) to best Alfred Borden (Christian Bale). Angier delves into teleportation, and Borden has a way to mimic himself as well (but if you haven't seen the movie I won't ruin the surprise). Anyway, the movie deals with this crisis of 'identity' and how originals and/or copies deal with the knowledge of the other.