Eu tive um problema semelhante recentemente - cartão diferente, tv 1080p. Para mim, alterar a taxa de atualização do meu monitor de 60Hz para 59Hz corrigiu o problema. Eu não sei porque (se alguém tem um palpite, por favor, deixe um comentário), mas a 59Hz a tela se encaixa na TV e em 60Hz era um pouco grande demais e parte da imagem foi cortada.
Então, tente alterar a taxa de atualização. No Win 7 é Painel de Controle \ Todos os Itens do Painel de Controle \ Exibir \ Resolução de Tela, clique em Configurações Avançadas e escolha a guia Monitor. Eu não sei o procedimento para o Ubuntu, mas deve estar nos documentos oficiais.