According to Apple: Time Machine "behaves correctly"

[Captain Code]

A while ago(before the GM build) I submitted a bug to Apple about how Time Machine wouldn't work any more with AFP mounted volumes and it had in the past worked.

Now they've just informed me that in order for it to work, the AFP volume must be on Leopard Server, and the share point must have "Enable Time Machine" checked.

This, IMO is a bunch of BS, and I think they just put it there to try and sell Leopard Server. There's no reason why it can't work over regular AFP volumes because I got it to work with
defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1