How full is your TDL? There is a limit of 100 items. If your TDL is maxed and you only have items scheduled for the next week, shows beyond that will appear in the Guide with a (R) but will not show in the TDL until other shows have been recorded and there's room to add them.
Also, I have seen instances in which a show that should be recorded has not shown up in the TDL until minutes before the show was to air.