Pedro,
*_How Should a Time Machine Hard Disk be Prepared?_*
For Time Machine to work properly, the hard disk must be formatted “Mac OS Extended (Journaled)” and its’ Partition Scheme should be either GUID or Apple Partition Map.
Time Machine is incompatible with disks partitioned as Master Boot Record (MBR). Unfortunately, this describes nearly every hard drive you can buy because MBR is a Windows partition scheme. (Naturally, this DOES NOT apply to Apples’ Time Capsule.)
For some, Time Machine begins to perform as expected with a new external hard disk. But then the initial full backup or subsequent incremental backups fail. The user only later discovers the hard disk was still partitioned as Master Boot Record (MBR).
One article on Time Machine made this observation: “Virtually everybody will have to open Disk Utility and repartition the disk as APM or GUID. It doesn't really matter which one because the Time Machine disk will not be bootable anyway. APM allows a disk to boot a PowerPC, GUID allows the disk to boot an Intel processor but both are easily digestible by Time Machine on either kind of processor.” [http://www.girr.org/mac_stuff/backups.html]
It’s been recommended by many here that your reserve +at least+ double the size of your primary hard disk, that way Time Machine backups have room to grow as the size of your data grows. Additionally, the more space you give Time Machine the more history it can preserve. The less space you reserve for Time Machine the sooner older backups & deleted items will disappear.
Procedure
Connect the hard disk you wish to use for Time Machine backups.
Launch Disk Utility.
It will appear twice in the pane on the left. (Make sure you recognize that it is different from the 2 icons that represent your Macs' internal drive.) The upper entry represent the device as a whole, including the controller inside. The lower entry represents the hard disk contained within the device.
Click on the upper icon of the external hard disk.
Select the "Partition" tab.
For "Volume Scheme" choose "1 partition". (Chose 2 partitions if you intend on storing other data on the disk besides your Time Machine backups.)
Name the disk.
Format should be "Mac OS Extended (Journaled)".
Click "Options".
Select either GUID or Apple Partition Map. (See above for significance)
Click "OK".
Click "Apply".
Now chose the level of secure erase you desire. (More passes means more time)
Once the external hard disk is repartitioned, select it again in Time Machine preferences and use it for your backups.
Let us know if this was helpful.
Cheers!