Buscando y buscando acerca de como cambiar el wallpaper en Windows 7 starter encontré una forma que funciona.
Para ello hay que descargar un programa llamado Oceanis desktop wallpaper (descargar).
Para cambiar el fondo hay que hacer lo siguiente.
Iniciar el programa, y luego buscar la imagen que queremos poner como fondo (1). Una vez que la tildamos en el buscador nos aparecerá en la lista de imágenes.
En ese momento debemos tildar la que querramos que aparezca como wallpaper (2). Por último hacemos clic en Save Changes (3).
Listo, así de simple, ahora disfruten de su Wallpaper.