So apparently you CAN NOT do this with a standard Airport Base-station and an external USB HDD connected to it and configured as an AirDisk.
There is a third party app that does it, but thats no good for a true automated backup utility.
Apple BETTER add an update to TimeMAchine soon that supports networked drives.