See http://hg.intevation.org/mercurial/crew/rev/d94832c4a31d
(patch: try harder to find the file to patch on file creation (issue2041))

Much simpler fix :)

diff --git a/mercurial/patch.py b/mercurial/patch.py
--- a/mercurial/patch.py
+++ b/mercurial/patch.py
@@ -934,7 +934,10 @@
 
     # some diff programs apparently produce create patches where the
     # afile is not /dev/null, but rather the same name as the bfile
-    if missing and afile == bfile:
+    abasedir = afile.rsplit('/', 1)[0]
+    bbasedir = bfile.rsplit('/', 1)[0]
+    if (missing and abasedir == bbasedir
+        and (afile.startswith(bfile) or bfile.startswith(afile))):
         # this isn't very pretty
         hunk.create = True
         if createfunc():

Ok this doesn't work because git patches don't work with this heuristic.

We should probably split this function and do something different for 
git/posix/gnu.

It fixes the issue and makes it closer to GNU patch, too bad we don't have 
extensive tests for patch formats.

diff --git a/mercurial/patch.py b/mercurial/patch.py
--- a/mercurial/patch.py
+++ b/mercurial/patch.py
@@ -920,6 +920,10 @@
             count -= 1
         return path[:i].lstrip(), path[i:].rstrip()
 
+    # not exactly the same as GNU diff, but close enough
+    def score(f):
+        return f.count('/'), len(f), f
+
     nulla = afile_orig == "/dev/null"
     nullb = bfile_orig == "/dev/null"
     abase, afile = pathstrip(afile_orig, strip)
@@ -930,11 +934,23 @@
     else:
         goodb = not nullb and os.path.exists(bfile)
     createfunc = hunk.createfile
-    missing = not goodb and not gooda and not createfunc()
 
+    candidates = []
+    if not nulla:
+        candidates.append(afile)
+    if not nullb:
+        candidates.append(bfile)
+
+    try:
+        fname = min(candidates, key=score)
+    except ValuError:
+        raise PatchError(_("undefined source and destination files"))
+
+
+    missing = not goodb and not gooda
     # some diff programs apparently produce create patches where the
     # afile is not /dev/null, but rather the same name as the bfile
-    if missing and afile == bfile:
+    if missing:
         # this isn't very pretty
         hunk.create = True
         if createfunc():
@@ -942,25 +958,6 @@
         else:
             hunk.create = False
 
-    # If afile is "a/b/foo" and bfile is "a/b/foo.orig" we assume the
-    # diff is between a file and its backup. In this case, the original
-    # file should be patched (see original mpatch code).
-    isbackup = (abase == bbase and bfile.startswith(afile))
-    fname = None
-    if not missing:
-        if gooda and goodb:
-            fname = isbackup and afile or bfile
-        elif gooda:
-            fname = afile
-
-    if not fname:
-        if not nullb:
-            fname = isbackup and afile or bfile
-        elif not nulla:
-            fname = afile
-        else:
-            raise PatchError(_("undefined source and destination files"))
-
     return fname, missing
 
 def scangitpatch(lr, firstline):

Any idea which `diff` created that? And how?

Same issue with import by the way, it's not mq related.

what is your `patch` binary?

we have a CVS+quilt workflow which migrated to hg as a hg+quilt workflow. in
theory i should be able to take my .patches directory from quilt and convert
it into a mq .hg/patches directory, i did this, and it mostly worked, except
for one hitch: new files. Attached is my reduced testcase based on the quilt
managed patch that failed.

timeless-mbp-2:qtest timeless$ hg qpop; hg qpush
popping a
patch queue now empty
applying a
unable to find 'a' for patching
1 out of 1 hunks FAILED -- saving rejects to file a.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh a
timeless-mbp-2:qtest timeless$ cat .hg/patches/a
--- foo/a.orig	2010-01-29 21:45:58.996136662 -0700
+++ foo/a	2010-02-12 06:33:45.000000000 -0700
@@ -0,0 +1,2 @@
+hello
+world
timeless-mbp-2:qtest timeless$ patch -p1 < .hg/patches/a
patching file a