Here are some more details about the problem as I have experienced it:
The problem is that saving from within Preview corrupts some PDF documents such that the text search and copy+paste functions no longer work properly. The text characters seem to be read as nonsense characters by the search and copy+paste functions. (For example, when I searched a document for "R", the search returned all of the "7"'s in the document.)
This problem occurs regardless of whether any annotations have been added to the document: simply openning a PDF in Preview and saving an additional copy of it using the "save as" function causes the search and copy+paste functions to be broken in the saved copy. (However, opening the same document in Adobe Reader and saving a copy does not cause this problem.)
As noted, in previous posts, this problem occurs with some PDF's, but not others.