Eu também estou executando o Ubuntu 16.04 x64 e confirmo que os dois aplicativos que você mencionou aparecem no Centro de Software no meu sistema.
O problema pode ser suas fontes de software. Verifique a tela "Software e atualizações" em "Configurações do sistema". A imagem abaixo mostra como a minha parece atualmente. Acredito que "Universe" seria necessário para o Unity Tweak Tool.
Tambémvaleapenaverificaroservidornalistasuspensa"Fazer o download de". Se você selecionar "outro", poderá testar o melhor servidor.
Espero que ajude.