You weren't having this problem on Tivo? It's really annoying when guide data isn't sufficient enough to fully use the capabilities of these devices. Comedy Central is the most annoying in this regard, IMO. Even Jon Stewart has made comments on the Daily Show about how Tivo owners will find 8 episodes of the show every day

I would just tell my Replay to record channel 354 at 11:30PM on weeknights (you're time may vary, but if you have DirecTV I imagine the channels are the same ).