Ao omitir / no início do caminho, você está especificando um caminho relativo, mas deseja especificar um caminho absoluto:
sudo gedit /var/lib/dpkg/status
Além disso, use gksudo para aplicativos gráficos. sudo não é realmente adequado para isso. Assim:
gksudo gedit /var/lib/dpkg/status
Veja Qual é a diferença entre “gksudo nautilus” e “sudo nautilus”? .