Whilst I was looking at Apple's Airport Extreme to see if it would replace my current Netgear DG834N (which isn't playing very nicely at all), I stumbled across a few projects that provide something akin to Leopard's Time Machine functionality for Linux.
The first is Flyback, a Google Code project based on rsync. It has a Python GUI interface to administer the backups and is extremely simple on the backend.
The next is TimeVault, an Ubuntu project. It integrates with Nautilus seamlessly to provide easy restore functionality. It works by watching directories for any changes and then keeping a backup copy of the files and directories that have changed. SQLite is used to keep a database of the backups and uses file hashing and an internal directory structure to store the actual file backups. Disk usage is reduced by using hardlinks to files that haven't changed.
All of these solutions lack the whizzy 3D interface that Time Machine provides but at the end of the day it's about the resilience and not the graphics. If you're running Linux, chances are that you don't need a 3D interface for your backup and restores anyway.