Сейчас в /usr/share/applications/celestia.desktop вообще нет категории. Стоит добавить что-то типа Categories=Astronomy;Education;Science; И репокоп перестанет ругаться, и у пользователя программа окажется в правильном подменю.