** see below - it does work! **
Today I discovered that under OS X Lion, backing up with Time Machine to an external hard drive on another computer over wireless is no longer possible. This worked under Snow Leopard, but apparently now Apple have decided not to support this any more. I guess they want us to buy Time Capsules, which are hard drives with their own wireless base station built into the shell. They are ridiculously overpriced and I won't be getting one! So I guess I'll have to just periodically plug my external hard drive into my laptop and back up like that. Not very impressed with that one Apple!
UPDATE: hmm maybe you can do it over afp shares, let me check that...
UPDATE: OK it does work over an afp share, so it will backup over wireless, but now of course it wants to start over, so it says the initial backup will take 3 days. sob!
UPDATE (30/4/2012): OK well the initial backup of 183 Gig took 4.5 days (!) but it did finish and now it works perfectly with the little incremental backups.
So, the answer is, set your backup directory on your external hard drive as am afp share using System Preferences > Sharing. Then when you can see it on your laptop, you'll be able to use it in Time Machine. The initial backup will take an age, but then it will work! Great :)