The patch was not created against the correct source tree.
One way this could happen:
Assume your original branch (the one you want to apply the patch to) has commits:
- 1a -> 1b -> 1c -> 1d
This branch is then cloned, and new commits are made:
- 1a -> 1b -> 1c -> 1d -> 1e
Commit 1e included old/filename
Now you do the work in the patch, based on the second branch, not the original one:
- 1a -> 1b -> 1c -> 1d -> 1e -> 1f
Commit 1f included the rename old/filename -> new/filename
Now, if you create a patch for commit 1f, you won't be able to apply it on top of commit 1d, because commit 1e is missing where old/filename was added to the index/repository.