After installing Encode via CPAN I got an error along the lines of 'Can't locate Encode/ConfigLocal.pm at line XX in Encode.pm'
After a quick google I found I needed to do
enc2xs -C
Now it works. I guess the Makefile could do with being fixed some to do enc2xs post installation
Have you reported the bug to Dan Kogai yet?