Sure you can. There's a command line hack that will allow Time Machine to use other filesystems/devices than HFS.
I'm currently running a Linux box with EXT3 filesystem. I have a Samba share that my iMac sees and mounts. Time machine uses this mount to back up to. The only difference is that files are stored as 8MB "sparse" files on my Linux box.
I've been running like this for months now, without any issues. My brother has the exact same set up, and hasn't had any issues either.
Gary