Lion AFP Time Machine Backups
Have you set it up like the Lion Server Administration article quoted below?

Time Machine service offers a backup destination on your server to Time Machine users. Use the Time Machine pane of the Server app to make server disk space available for backing up users’ computers, or to change the disk used for storing user backups.  

Time Machine service is available to users with Mac OS X Lion, Snow Leopard, and Leopard. Mac OS X Lion and Snow Leopard users who haven’t selected a backup disk in the Time Machine pane of System Preferences are automatically asked whether they want to use the server as a storage location. Other users need to open the Time Machine pane of System Preferences and change the backup disk.




In the Server app sidebar, select Time Machine.
Click the On/Off switch to turn on Time Machine service.
Select a disk to use as the destination for users’ backups, and then click Use for Backup.
Time Machine service creates the Backups shared folder on the disk you select.




To choose a different disk as the backup destination, click Edit.
If you turn on Time Machine service when file sharing service is off, file sharing service turns on automatically.

If you change the backup disk, users’ Time Machine preferences that were set to use the server for backup storage will automatically begin using the Backups folder in its new location.

After selecting a different backup disk, advise users that their first backup will take longer because it’s a full backup. Time Machine service doesn’t copy users’ backup data from the old Backups folder to the new Backups folder.

You can control each user’s access to the server’s Time Machine backup storage in the Users pane of the Server app.