afpサーバのnetatalkがバージョン2.0.5でTime Machine対応してました。
さっそくサーバにインストール。CentOS 4.4で使えるRPMを見つけられなかったので、ソースからmake install。
sambaでTime Machineするためのおまじない解いても、確かにTime Machineとして認識されます。今後はafpでサービスしようと思います。
ただ、Time Machineでディスクを選択させるには、いったんFinderでマウント（サーバへ接続でafp://xxxxというように）させておかないと選択に現れないです。一度選択してしまえば、その後は問題なく使えるので、とりあえずOKです。
常に見えるようにするには、サーバ側にBonjourを入れなければならないようです。
これをやっておかないと、DVD起動させてTime Machineからの復元を行う際にTime Machineドライブが見えずに困ってしまいます。