With Lucid (or 10.04) Ubuntu now ships with Kerberos 5 version 1.8 which, by default, blocks DES encryption. While it is laudable, as DES certainly is weak by today’s standards, it unfortunately breaks AFS in it’s current form. To get it working, you need to modify /etc/krb5.conf:
[libdefaults] allow_weak_crypto = true