a que distribución pasaste?? Mira, al parecer el paquete esta corrupto, esto es habitual en sid, así que tendras que esperar un poco a que lo compongan, ahora, si pasate a sarge, pues entonces puedes tratar de desinstalar sed y despues volverlo a instalar solito con apt-get.