Before You Use OS X Time Machine

When you buy a hard drive that you will use with Time Machine, the first thing you do after connecting it to your Mac should be this (the instructions are for the current version of Mac OS X, which is 10.5.6):

1. Open Disk Utility
2. Select the new hard drive
3. Go to the Partition tab
4. Choose the number of volumes (normally one) from the Volume Scheme dropdown 
5. Click on the Options… button
6. Choose GUID Partition Table or Apple Partition Map depending on whether your Mac is Intel-based or PowerPC-based.
7. Click Apply.

Source: www.456bereastreet.com