Corrigido o problema. Obrigado aos caras do Bugzilla do GNOME. Eu relatei esse problema lá e eles foram rápidos em responder.
Aparentemente, um dos arquivos .desktop tinha codificação incorreta do nome do arquivo (um aplicativo estúpido do Windows que eu instalei usando o wine).
Esses arquivos estão localizados em ~/.local/share/applications ou /usr/share/applications . Ao renomeá-lo, meus ícones de aplicativos estavam de volta.
Novamente, obrigado a Jasper St. Pierre no GNOME.