Are the tuners busy? Example - are you using the tuners in other applications or machines, in addition to the machine doing the MC recording? do you have more recordings scheduled than tuners available? etc.
If you go to MC standard view and look at Television > Server Tv Logs > are you seeing errors? are you seeing correct start times and end times? are you seeing the EPG Load happening at the correct times?