Time Machine with NAS
I've written previously about Time Capsule's problems and my preferred alternative of using Airport Extreme and an external hard drive. Another option worth considering would be a Network-attached storage (NAS) device.
QNAP, a company that makes NAS devices, has a forum post titled "How to use your NAS with Time Machine" that explains the setup procedure, which is similar to the procedure for setting up Airport Extreme with an external hard drive.
Here's another tutorial for another company called Synology that makes similar products:
And here are similar instructions for a Netgear ReadyNAS: http://www.readynas.com/?p=253
Finally, AppleInsider has the most thorough piece I've seen assessing Time Capsule and its performance: