Acabei com uma solução realmente simples e fácil, mas resultou em um pouco de perda de dados.
Eu tinha desistido do grub depois de muitas tentativas fracassadas de reinstalar o arquivo e foi resignado apenas a reformatar a partição e reinstalar o Ubuntu, e notei a opção de reinstalar o 11.04 em cima da minha cópia atual após iniciando o instalador.
Eu re-instalei e precisei ter uma nova cópia do grub configurada corretamente durante essa etapa. Apenas o efeito colateral foi a maioria dos meus aplicativos que eu tinha instalado através do softwarecenter estavam faltando, mas quando eu os reinstalei, as configurações ainda estavam lá.
Após 20 ou 30 minutos de reinstalação dos aplicativos, o rEFIt e as duas instalações do SO estão funcionando da mesma maneira que antes da instalação do Lion.