Ok, I have found the fix. I'm not sure I understand what is going on under the hood, but the fix is to use the Encode library and instead of assigning it directly as such:

$x = "files/$state/$type/thing.pdf"

I use the results of encode to assign it instead:

$x = encode('UTF-8', "files/$state/$type/thing.pdf", Encode::FB_CROAK);

Tracing through the CAM::PDF code showed the data in the success path was looking like straight hex (AFDDECBB), while in the failure path it was showing as such: (\x{af}\x{dd}\x{ec}\x{bb}).

Humans can't see any difference between $x, but perl sees something really different.