With the help of some C++ gurus I found the answer.
You need to explicitly provide a definition of lengthof::array_size.
Just declaring it in the class isn't enough:
namespace Private {
template <class T> struct lengthof;
template <class T, size_t N> struct lengthof<T[N]> { static
const size_t array_size = N; };
template <class T, size_t N> const size_t
lengthof<T[N]>::array_size;
}
Man, GCC4 is testing all of our C++ knowledge to the limits!

Funny
how no other compiler needs this, and even GCC4 doesn't need it most of
the time.