This sounds like address translation lossage.  Try a numeric address.

  Are there any known library problems that would cause this? The server is
  running Linux kernel 2.2.16, libc version 2.1.3.

It's highly likely :-)  My systems are all FreeBSD and NetBSD.  Still,
even without libc-of-the-week flakiness, I've had problems that seem
somewhat similar.  I suspect that something in venus isn't 100% right
with respect to hostname lookup, but I have never figured it out.

If I were faced with your problem, I'd look at
coda-src/venus/comm.c:210, and then add more robust error checking and
diagnostics above.  For example, there are no diagnostics if
gethostbyname fails, and the following might help:

Index: comm.cc
===================================================================
RCS file: /coda-src/coda/coda-src/venus/comm.cc,v
retrieving revision 4.63
diff -u -u -r4.63 comm.cc
--- comm.cc	2000/10/18 12:14:37	4.63
+++ comm.cc	2000/10/20 14:31:37
@@ -200,6 +200,8 @@
 	    s = new srvent(&addr, 1);
 	} else if ((h = gethostbyname(ServerName)) != NULL) {
 	    s = new srvent((struct in_addr *)h->h_addr, 1);
+	} else {
+            eprint("Couldn't get IP address for Server %s", ServerName);
 	}
         if (s != NULL) {
 	    srvent::srvtab->insert(&s->tblhandle);