Talvez, primeiro tente isto:
apt-get install -y parted (in case of Debian-based distro)
partprobe
parted /dev/sda
u s (switches units to sectors)
p (prints partition table)
mkpart p start end (p - primary, this should be your sda3)
mkpart p start end (should be sda4)
Eu corri partprobe novamente depois disso. Se isso não funcionar - então, sim, seria necessário editar o MBR manualmente, eu acho.
Editar : uma coisa que me ocorreu é que você pode ter problemas, quando o parted está reclamando de injetar partições com limites "fora da especificação". Bem, basta excluir tudo a partir de sda5 e recriá-los da mesma maneira após a adição bem-sucedida de sda3 & sda4 .