Perhaps http://sources.redhat.com/ml/binutils/2011-08/msg00011.html ? 
And/or it might be related to the local ppc64 change in our gcc (for many years now):
+#ifdef HAVE_LD_OVERLAPPING_OPD
+/* If the linker supports overlapping .opd entries and we know this function
+   doesn't ever use r11 passed to it, we can overlap the fd_aux function
+   descriptor field with next function descriptor's fd_func field.  */
+# define OVERLAPPING_OPD (cfun->static_chain_decl == NULL)
+#else
+# define OVERLAPPING_OPD 0
+#endif
...
@@ -25938,7 +25925,8 @@ rs6000_elf_declare_function_name (FILE *
       ASM_OUTPUT_LABEL (file, name);
       fputs (DOUBLE_INT_ASM_OP, file);
       rs6000_output_function_entry (file, name);
-      fputs (",.TOC.@tocbase,0\n\t.previous\n", file);
+      fprintf (file, ",.TOC.@tocbase%s\n\t.previous\n",
+              OVERLAPPING_OPD ? "" : ",0");
       if (DOT_SYMBOLS)
        {
          fputs ("\t.size\t", file);
where we emit just 16 byte .opd entries instead of 24 bytes if we can ignore the r11 value in the function.

Alan, do you have any ideas what might be wrong here?

Peter, Jakub quizzed me earlier today on this bug.  I replied that the opd squashing won't affect stub sizing as far as I can see.  I'm guessing that binutils-2.21.53.0.1-1.fc16 has my 2011-07-14 change included, which had a bug in stub sizing, fixed here:

2011-08-02  Alan Modra  <amodra@gmail.com>

	* elf64-ppc.c (build_plt_stub): Correct emitted relocs when no
	plt_static_chain.
	(ppc_build_one_stub): Adjust get_relocs call to suit..
	(ppc_size_one_stub): ..and reloc sizing.  Correct plt size corner case.
	                                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah, I guess I misunderstood what Jakub was saying.  I thought Jakub was pointing at your patch as the culprit and not as a potential fix.  Ok, so it seems fedora just needs to grab your latest fix and we should be good.  Thanks.

binutils-2.21.53.0.1-6.fc16 has been submitted as an update for Fedora 16.
https://admin.fedoraproject.org/updates/binutils-2.21.53.0.1-6.fc16

Package binutils-2.21.53.0.1-6.fc16:
* should fix your issue,
* was pushed to the Fedora 16 testing repository,
* should be available at your local mirror within two days.
Update it with:
# su -c 'yum update --enablerepo=updates-testing binutils-2.21.53.0.1-6.fc16'
as soon as you are able to.
Please go to the following url:
https://admin.fedoraproject.org/updates/FEDORA-2011-17104/binutils-2.21.53.0.1-6.fc16
then log in and leave karma (feedback).

binutils-2.21.53.0.1-6.fc16 has been pushed to the Fedora 16 stable repository.  If problems still persist, please make note of it in this bug report.