Why can't templates be within extern "C" blocks?

Templates aren't actual code, they're just guidelines to the compiler for how to generate the code once the template parameters are known. As such they don't actually exist until you try to use them. You can't provide linkage to something that doesn't exist.

What does it mean that a template "may" have linkage? What is template linkage?

All names either have external linkage, internal linkage, or have no linkage (C++03 §3.5p2), but this is not the same linkage as language linkage. (Confusing, I know. C++0x changes things around considerably with linkage, too.) External linkage is required for anything used as a template argument:

void f() {
  struct S {};
  vector<S> v;  // Not allowed as S has internal linkage.
}

Notice that C++98 has "may" in what you quoted of §14p4, but C++03 removes the "may", as templates cannot be declared in a context that would give them internal linkage:

void f() {
  // Not allowed:
  template<class T>
  struct S {};
}

Because extern C disables name mangling, which templates use

To see that templates are implemented with name mangling, compile and decompile:

#include <cassert>

template <class C>
C f(C i) { return i; }

int main() {
    f<int>(1);
    f<double>(1.5);
}

with:

g++ -c -g -std=c++98 main.cpp
objdump -Sr main.o

The output contains:

int main() {
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   48 83 ec 10             sub    $0x10,%rsp
    f<int>(1);
   8:   bf 01 00 00 00          mov    $0x1,%edi
   d:   e8 00 00 00 00          callq  12 <main+0x12>
            e: R_X86_64_PC32    _Z1fIiET_S0_-0x4
    f<double>(1.5);
  12:   48 b8 00 00 00 00 00    movabs $0x3ff8000000000000,%rax
  19:   00 f8 3f 
  1c:   48 89 45 f8             mov    %rax,-0x8(%rbp)
  20:   f2 0f 10 45 f8          movsd  -0x8(%rbp),%xmm0
  25:   e8 00 00 00 00          callq  2a <main+0x2a>
            26: R_X86_64_PC32   _Z1fIdET_S0_-0x4
}
  2a:   b8 00 00 00 00          mov    $0x0,%eax
  2f:   c9                      leaveq 
  30:   c3                      retq

Note how all callq were made to call weird names like _Z1fIiET_S0_.

The same goes for other features which depend on name mangling, e.g. function overloading.

I have written a more detailed answer at: What is the effect of extern "C" in C++?