На моем 11.04, libgcj-bc - версия 4.5.2-1, которая удовлетворяет зависимостям. Вероятно, это означает, что вы поймали новую версию с помощью PPA, backports или других средств. Откройте синаптический режим, выберите libgcj-bc, нажмите Ctrl + E и выберите версию ниже 4.6.
Это должно решить установку pdf-tk, но может привести к другим проблемам с зависимостями, которые могут быть устранены путем удаления зависимых пакетов и установить дистрибутивы. Тем не менее, может быть разумнее ждать 11.10, где доступны более свежие пакеты.