"Time Machine could not be configured. The built-in network interface could not be found." - I'm on 10.5.6 by the way (the error was less informative before).
I can set up networking either wirelessly or with a USB ethernet dongle (the one for the Air seems to work these days), but Time Machine won't let me choose a backup volume.
Weird thing is that I can configure the on-board ethernet port, it has a mac address it just permanently looks to be unplugged.
The other interesting thing about this is that Time Machine works on a MacBook Air which only has wireless or USB networking.
Got it working by doing this as root:
mv /Library/Preferences/SystemConfiguration/NetworkInterfaces.plist /Library/Preferences/SystemConfiguration/NetworkInterfaces.plist.old
Rebooted, went to Network System Preferences, tidied up the network interfaces (deleted bluetooth, a serial device, and the Firewire device) and re-configured Time Machine.
Anyway, it's good to back on the Time Machine routine again.