Você não especifica qual versão do Ubuntu você está usando, mas para 16.10 o Kodi 16.1 está disponível no repositório oficial (universo):
Dependendo da sua versão do Ubuntu, você pode usar diferentes estratégias para instalá-lo.
Para 16.04, até o Kodi 15.2 está disponível: