The issue isn't partitions. When you are in the Partitions section hit the "Options" button and make sure your drive is set up to use the GUID method of addressing rather than Master Boot Record. That should solve your problem of the drive not appearing/being recognized.
HTH,
Rez
There seems to be some confusion on how to enable so here are the steps hope they help someone out there out:
1.If you have a disk already plugged into your AEBS it may or may not work. I suggest you start by going to your System Preferences, Time Machine and see if your Airport Disk shows up. If it does then sweet you are all set!
2. Assuming it does not show up first open finder and attempt to browse your Airport disk, once you have opened a folder on it go back to the System Preferences, Time Machine and see if it shows up. If not proceed to step 3.
3. If you are like me it still wasnt showing up. The steps were to first backup the files on your AirDisk to some other safe location. Then plug the USB drive into your Mac, open disk utility and format it Mac OS Journaled hook it back up to your AEBS. Open finder and browse the AirDisk, then proceed to System Preferences, Time Machine and you should be good to go!
Still not working for me. I selected the "GUID Partition Table" under "Options." Should I have selected something different?