In the end, I was able to solve this problem by explicitly installing Encode before processing the other dependencies in the cpanfile. I'm still not sure why enc2xs wasn't present earlier even though Encode was, but I'm glad to have it working.