The databases were fully backupped once?

Databases are in full/bulk logging mode?

Perhaps there are long running transactions/replications going on

You could convert the maintance plan to a normal job to see what's going wrong.

BACKUP LOG DATABASE X TO DISK='X:\AdventureWorks.TRN'

backup log command[/url]

Or use Ola's backup script as a replacement for the backup/index maintenance plans

Ola Hallengren[/url]