Not properly supporting the frame before cutting into it is usually where this goes wrong, right at the beginning.
I really doubt the bed itself is sagging; too much rigidity in too many places for that. The sagging appearance is almost surely going to be perception from comparing cab to bed body lines and the gap between them, and it'll be because the frame is sagging at the notch.
Thousands upon thousands of bolt-in C notches have been performed with no issues - when done to the letter of the instructions. A bolt-in C notch is not the problem.
As far as correcting it? Tough call as I haven't had to fix one afterwards, but here's a guess at what might work. Pull the bed, take some measurements on top of the frame to see if the rails are straight or not. A nice long straight edge across the notch should show the issue. If the holes were drilled correct size, this is where the battle comes in as you won't have slack for adjustment (and this is actually a good thing, as Hipster mentioned, holes too large that would allow you to adjust are also what would allow it to get out of place and flex.) I would imagine at this point your best bet is to loosen the bolts, remove most of them but leave one snug at each end of the notch to hold the notch brace in place, jack the frame up at different points until you can measure it nice and straight across. Support it with stands and weld the notch into place.
Definitely open to hearing other opinions on what I just suggested, I'm not saying it's "the" fix, it's just a guess at what might work.
Richard