The most common cause of the first backup to an external HD failing is the Time Machine drive/partition not being formatted correctly.  Use Disk Utility (in your Applications/Utilities folder) to verify the setup:

First, select the second line for your Startup drive (internal HD) usually named Macintosh HD.

Towards the bottom, the Format should be Mac OS Extended (Journaled), although it might be Mac OS Extended (Case-sensitive, Journaled).

On Lion, it may also be encrypted.

Next, select the line for your Time Machine partition (indented, with the name that you selected in TM Preferences).

Towards the bottom, the Format should almost always be the same as your Startup drive (above), except the backups on Lion may be encrypted.  If they're not the same (one is case-sensitive and the other is not), see the pink box in Frequently Asked Question #5. The only way to change the Format is to erase the partition and select a different format.

Last, select the top line of the Time Machine drive (with the make and size).  Towards the bottom, the Partition Map Scheme must be either GUID or Apple Partition Map.  Either will work for Time Machine;  but for some other purposes, GUID is preferred for an Intel Mac, Apple Partition Map for a PPC Mac.  If this is wrong, you must completely erase the disk and reformat it.  See Frequently Asked Question #5.

Once you're sure your disk/partition is formatted correctly, if your backups still fail, continue to the next item, #C2.

7/20/11

Copyright © 2011 James Pond.  All rights reserved.