A simple (sudo) gem install iconv should do the trick. pdfbeads has some minor issues like that, unfortunately. I'd have preferred to investigate them at the source, but Rubyforge closed down last year and there doesn't seem to be a new location for it as far as I've been able to tell with a quick search.
PS Also see what I wrote
here.