I just received an update from my customer on this. Apparently they have the PTF applied already.
IBM support is saying to try adding the library that the QZHBCGI object is in to the library list. QZHBCGI is a service program. The eRPG SDK service programs are created using binding directories pointing directly to this object (the library is stated in the Binding Directory).
A better option would be to copy the QZHBCGI object into their CGI library, but that still doesn't explain the fact that it's worked since V5Rx up until now (with that one issue from V5R3 to V5R4 mentioned previously that was fixed with a PTF and seems to be exactly the same problem as this).
So, again IBM support I don't believe is looking deep enough. They're focusing on one error in the job log which is that the QZHBCGI object is not found in *LIBL.
I will update when I hear more.