Observe que os problemas que você está enfrentando se aplicam ao boot no modo herdado. (Sua tabela de partições no gparted dirá msdos) Se você usar o GPT com BIOS ou UEFI, isso não se aplica.
error: no such partition. entering rescue mode. Implica que o grub não pode carregar módulos e que o sistema de arquivos no mesmo disco não pode mais ser encontrado. Na terminologia de grubs, isso é chamado de estágio 2. Isso ocorre porque sua partição / boot foi excluída ou formatada. Isso também se aplica se sua raiz foi excluída contendo um diretório / boot.
Você pode tentar simplesmente recriar a partição de inicialização se ela foi excluída, já que o espaço não alocado no início do disco de cerca de 500 MB era provavelmente sua partição de inicialização.
No gparted, você pode selecionar o espaço não alocado e criar uma nova partição, mas ao criá-la, o tipo de sistema de arquivos não será formatado. Isto é muito importante. O padrão será ocupar todo o espaço livre contínuo e será uma partição primária. O espaço livre anterior e seguinte deve ser 0 Depois disso, clique em aplicar e depois que ele for carregado, ele detectará que o ext3 ou ext4 funcionou. Isso não é uma prova completa e você pode querer usar o testdisk para encontrar automaticamente partições perdidas.