Windows server 2008 r2: Backup notifications

Yes, this is expected behavior. In order for the transaction logs to be useful, there needs to be a full backup to use as a starting point for rolling forward.

Don't worry about it too much. If you create a new database, the first day you will get that error. The log backups for the other DBs will succeed, as you saw, but that error will just make it LOOK like the step failed when in reality only the one DB failed. Then, that night (or whenever), it will do the full backup. After that, the trans log backups will be successful for the new DB. Basically, you would have one day or errors when you create a new DB until the full backup job runs.

I do something similar, except instead of renaming the folder afterwards, I create a new folder before doing the backup, like this:

cmd /c mkdir \\remotebackuplocation\somefolder\%DATE% //(%DATE% will obviously not work well if you have slashes in your date string, but that's easily fixed with some character replacing)
cmd /c wbadmin start backup -backupTarget:\\remotebackuplocation\somefolder\%DATE% -include:C: -vssFull -quiet

You can list all your backups with this command

wbadmin get versions

Then this command to restore

wbadmin start recovery -version:<version-identifier>

wbadmin command reference