The problem is that kpsewhich is looking for files in /usr/share, but /usr/share is not in $PATH so it doesn't know to look there. To solve this, I added /usr/share to the root $PATH by doing:
$ sudo -s
# $PATH=$PATH:/usr/share
# sudo apt-get install <whatever was causing the problem>
The problem is that kpsewhich is looking for files in /usr/share, but /usr/share is not in $PATH so it doesn't know to look there. To solve this, I added /usr/share to the root $PATH by doing:
$ sudo -s PATH:/usr/ share
# $PATH=$
# sudo apt-get install <whatever was causing the problem>
and it should work fine!