So is this a fresh start with Lion?
Are you backing up over existing SL backup?
Many a slip here.. you need to get the actual error message if there is one..
Are you doing this via wireless connection?? DON'T.. use ethernet at least for the first large backups.
Read the troubleshooting remedies.
In addition to LaPastenague's suggestions:
Are you backing-up to an external HD? If so, does it have the GUID (preferred) or APM Partition Map Scheme? Check it via #C1 in Time Machine - Troubleshooting