But to me the first could mean :
I am certain he wasn't hungry.
(Similar to a sentence: "He must have not seen it coming")
The 2nd line would mean:
It's impossible that he was hungry.
Well, he must not be the thief they're looking for then. (We'd better let him go)
Well, he can't be the thief. (He wasn't anywhere near the victim during that time. You can't arrest him.)
Here's a situation:
"I waved at your wife but she kept on walking, she must not have seen me (i'm sure she didn't see me)."
"Well, she couldn't/can't have (of course that's impossible for her to see you), because you were waving at her from the third floor."