Hi Jon,
Do you have tuning adapters? You can see this error with tuning adapters (generally Cisco’s) take too long to tune request a channel. If so, what happens is:
1- Media Center attempts to record on Tuner X.
2- The tuning adapter takes too long to respond
3- Media Center does not see a signal on Tuner X soon enough so it reports failure
4- Media Center attempts to record on Tuner Y
5- The channel was already allocated in step #2 so the tune request responds quickly
6- Everything records properly but has the failed message from Tuner X
Note: Lots of steps left out (i.e. oversimplified)