Regarding your question: Yes, the +
lines are lines added by the patch. Removed lines would have a -
in front.
Regarding the general problem, depending on how many patches you have, and depending on the amount of errors you get, one of the following could work for you:
If you have any chance to get the version on which a patch is based upon (e.g. from your CVS), apply the patch to this version. Then try your luck by comparing against the current version you have and incorporate the changes.
If it is only a few files out of a set of significantly more files to be patched (e.g. 1 out of 10) make a copy of the patch file, remove the changes that cause errors and apply the rest. Then try to apply the changes removed from the patch file in another way. This will work for few rejections, but becomes a PITA with large or lots of rejected patch sections.
Have the patch creator rebasing the patch (assumed it is someone else).