O suporte embutido para placas ATI no Ubuntu 9.04 é melhor. Você não deveria precisar do fglrx.
Eu sugiro fazer algum tipo de teste de instalação limpa, embora talvez o Live CD seja suficiente para verificar se os drivers ATI padrão do ubuntu funcionarão para o seu sistema.
O motivo de sugerir instalação limpa é que as personalizações para o Vídeo (por exemplo, uso direto do fglrx em vez de usar o menu "drivers de hardware") e personalizações para rede (por exemplo, usando o ndiswrapper) confundam o processo de atualização.
Depois de bater minha cabeça contra estranhos problemas de vídeo (e problemas de rede) após uma atualização, resolvi meus problemas com um backup dos meus dados, incluindo o diretório .mozilla, uma lista de pacotes instalados, uma instalação limpa e uma restauração manual do meu ambiente desejado.