Hm... Parece que a hal do sistema pode ter danificado. Oh, o problema que já misturou atualizações de pacotes de outros repositórios não oficiais. Se conseguir iniciar normalmente, recomendo que veja o histórico do Synaptic e "reabaixe" os pacotes para versões mais antigas. Agora se puder fazer, mesmo não sendo a melhor solução, te recomendo reinstalar mesmo o sistema e usar só os repositórios oficiais do Ubuntu para atualizações. Não digo para não usa outros para instalar programas. Eu mesmo uso outro repositório, no caso o do Debuntu para pegar o Gaim mais novo. Mas ele é super confiável. Outro que uso é do amarok, mas esse não conta porque é oficial do Kubuntu. Agora os outros habilito só pra instalar os programas e depois desabilito para não ficar atualizando. Por exemplo, tinha um repositório do Beryl que eu usava e detonava meu sistema toda vez que saía uma atualização. Depois arrumei um outro que era na boa.
Uma pergunta: qual sua placa mãe? E os chipsets dela são de qual fabricante (Nvidia, VIA, SiS, ATI, Intel...)?