No se si el_lobo te ha entendido mal o estaba un poco de coña... Porque si restauras, vuelves a dejar todo como estaba (de fábrica vamos).
Y no hay que "hacer nada" respecto a lo que dices. A lo sumo un reinicio del teléfono, pero si has eliminado correctamente las aplicaciones, ese espacio ya debiera estar "disponible". Si aún así, no lo "ves", se pueden pasar algunas aplicaciones de la carpeta system/data a system/app. En data se instala todo lo que bajas del market o instalas desde la sd. En app están las aplicaciones de sistema propiamente, las que ya traía el teléfono. Puede ser por ese motivo que no "veas" ese espacio libre.