Sorry that you missed your episode. I'm not sure of the CBS scheduling details, so I'll just blather in generalities.
Pre-emptions present a special challenge to DVR scheduling. We get daily updates to the guide information from a syndicated service (Tribune Media Services--same folks who supply most newspapers, TiVo, as well as several online TV listings sites.)
If there's a sudden pre-emption, for example, for breaking news, the DVR guide data doesn't know about it. So, typically, the DVR will record whatever is broadcast at that time on that channel, and mark it down as a successful recording.
The big gotcha is not whether you have set an option for "first run only," but rather a set of rules that tries to avoid duplicate recordings of the same episode within a certain timeframe. If we can detect that an identical episode is being repeated (based on the guide listings), then we'll only record it once. Doesn't matter whether you set first-run only. We want to avoid filling your drive with multiple copies of an identical episode. (Sometimes there is no episode data in the listings, so the DVR has no way to spot the duplicates. In those cases, it's still possible to get multiple copies of the same episode.)
So, if CBS pre-empts a listed show after the guide data is updated, your DVR will record whatever replaced the originally scheduled show, but it thinks it has actually recorded the program you asked for. That's where the trouble starts.
Now the network reschedules the missed episode. Humans know this is actually the first airing. But the DVR thinks it has already successfully recorded that episode. So, the DVR invokes the "no duplicates" rule and doesn't record it "again."
If you know about a pre-emption, you'll need to manually set a "record once" request for the rescheduled airing.