Tim,

Normally this means that there was an incremental
backup (or even a full) that contains logs that
you may also need to restore.

When you restore just the public or private part of the
Information Store, we can't erase existing log files
since the non-restored part of the Information Store
requires those other logs for integrity.
Clear as mud, right?  How about an example.

Say for example, the current log files are:

edb00010.log
edb00011.log
edb00012.log

And you restored the private part of the IS
and the associated logs, say:

edb00004.log
edb00005.log
edb00006.log

The Exchange Server DEMANDS logs:

edb00007.log
edb00008.log
edb00009.log

or it won't start up correctly.

If those logs are in an incremental, then just restore them.
But, if you are trying to "backlevel" only that part of
the store, and you have taken more full backups in between,
then you will have to try another procedure, like restore
to an alternate server and copy out what you want.

Thanks,

Del