I came across this, which recommends running this command in Terminal (all one line):
defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1

Which will cause mounted network volumes to be accessible to Time Machine.

I haven't tried this yet, but reports are that further effort needs to be made, at least under 10.5.2. So just in case this is still a problem (my iMac is now at 10.5.6), here are some instructions (taken from here):

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Backing up Macs to WHS using Time Machine on OSX 10.5.2:

1. First install required update. This fix is required in OS X ver 10.5.2 to improve Time Machine SMB handling (SMB is a protocol used between PCs for regular file sharing in a LAN). This update also fixes some bugs in the wireless network support. This fix can be downloaded from Apple. Without this fix our Mac crashed when 20% of backup was done. Link: http://www.apple.com/support/downloads/timemachineandairportupdatesv10.html

2. Start finder and connect to the network backup share on the WHS server.

3. The setting TMShowUnsupportedNetworkVolumes=1 needs to be in the systempreferences for the SMB share to be selectable as a Time Machine destination. This can easiest be done by starting a terminal session and enter defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1

You may check that it is correctly written by giving the command defaults read and finding the entry near the end of the systempreferences file.

4. Go to Time Machine settings and select the share as destination - it should now be visible.

5. The backup should now start automatically after 120 s. In OSX 10.5.2 the backup will fail but you should be able to save the name of the file in the WHS share catalog before the file becomes deleted after a minute or so. The file is called something like "machine name"_wireless mac adress.sparsebundle. If your machine name contains spaces or is longer than 8 characters, change it. Make sure your machine name does not include spaces, symbols, etc. (just numbers and letters) and keeping the name of under 8 characters before starting the backup attempt. Backup can be restarted by deselecting the destination folder, and then reselecting it. What you need is the sparsebundle file name. (A eight alphanumeric machine name is maybe not needed with the fix mentioned above - but I changed it anyway)

6. Open the program Disk Utility to manually create a sparsebundle. The Help file tells you how. Use the first part of the filename "machine name"_wireless mac adress but leave the .sparsebundle out. As part of the creation process, you will be prompted to assign a size to the sparsebundle. Select a size less than that of your NAS volume's physical capacity (and it is probably a good idea to leave an ample amount headroom so that Time Machine has space to do its thing, minimum the size of the disk being backed up). The file will typically be less than 100Mbyte when it is created so don't worry about the size for now. Put it on your desktop. Unfortunately, I can only vaguely describe the settings for this file since the setting naming on our system is in Norwegian but here is at least some clues: No partition, no encryption, format MAC OS extended journalled standard, packeted disc image.

7. Copy the newly created sparsebundle file to the WHS share root. Make sure there is no trace left of the previous attempts to create the file. Also delete any .xxxxxxxxx files in the root (this is maybe only valid on non-WHS Linux based NAS?). In WHS Explorer the sparsebundle file will be shown as a folder. When you have it on the share, delete it from the desktop, but save the name - you might need it again.

8. Remove the backup share from Spotlight. It helps makes things go faster. Go to System Preferences - Spotlight, then under the "privacy" tab, click on the Plus sign and add the backup share under devices.

9. On the WHS console disable duplication on the share used for Time Machine backups (This is as a safety measure for as long the data corruption bug still exists)

10. Now start the Backup by selecting the WHS share as destination in Time Machine settings.

Following this procedure our backup presumably works, at least for now backing up from MacBook Air via WiFi to a HP WHS. Unfortunately it runs quite slow so testing takes time. Also, restore is still untested. As one can see, this is quite complex and there is many things that can go wrong so "shrink wrap" SW should be developed.

Here are the sources used to put together this procedure:
http://www.macosxhints.com/article.php?story=20080420211034137
http://www.99.se/mac-os-x/242612-att-f-time-machine-att-fungera-med-windowsserver-via-samba.html (Swedish)
http://babygotmac.com/a/leopard-1052-airport-express-and-time-machine/
http://www.tuaw.com/2008/03/19/time-machine-and-airport-updates-1-0/
http://uneasysilence.com/archive/2007/10/12595/