Had this error on an old SQL 2000 instance where the server had disk capacity issues. The Database Maintenance Plan that was configured worked perfectly in every way except for the removal of transaction log backups that were older than a certain age.
I found this article which explained perfectly the symptoms that I was having http://support.microsoft.com/kb/303292
The Maintenance Plan did not meet best practice and there was just one plan that backed up the databases and transaction logs of all databases regardless of whether they were a system database (Master, Model, MSDB) or user databases in SIMPLE or FULL recovery mode.
A transaction log backup command against a database that is configured in SIMPLE recovery mode will cause an error message. There is a known bug within SQL 2000 that results in the Transaction Log backup continuing after this error to the next database but essentially it completes the process but without removing the expired TL backups.
For me this was a good opportunity to start again with the DB Maintenance Plans. I manually deleted the expired TL backups to reclaim hard disk capacity and then created 3 new DB Maintenance Plans. These were:
1. System DB Maintenance Plan – Includes optimisation, database backup
This is as per Microsoft guidance. Always backup system databases (Master, Model, MSDB) separately to user databases for resiliance
2. Full Recovery DB Maintenance Plan – Includes optimisation, database backup, transaction log backup
3. Simple Recovery DB Maintenance Plan – Includes optimisation, database backup
Microsoft also offer another alternative which is to change all your databases to FULL recovery but to me this is unneccessary when you have carried out risk analysis on your databases and have the correct maintenance plans in place.