Problem obtaining tokens

I am experiencing a problem while obtaining tokens:

1) when I use the afs_credentials program to obtain the tokens it fails with a 
message ("afs service is not started" or so). Nevertheless, it seems to be 
able to communicate with the afs server, since it tells me when I enter an 
incorrect password.

2) I found a workaround by accident: If I connect to a VPN account and try to 
obtain the token while the VPN connection is active, the tokens are returned 
successfully as soon as I quit the VPN connection (only sometimes though). As 
soon as I have one token it is no problem at all to get a token for another 
cell. All the AFS connections are working excellent from that point. The only 
critical issue is obtaining the first token.

I am sorry that I can not be more specific about that issue, I wish I could. 
Does anybody have a clue what could be the reason for the strange behavior.

The behavior is the same in 1.3.70/71/73.

Best regards,  Rudi