I thought Windows 7 starter was the version where you couldn't change the desktop background. Turns out the usual way of changing the desktop background is not present in Windows 7 Home Basic as well. If you right click on the desktop in Windows 7 Home Basic the option to personalize the appearance of the desktop is not present. However, unlike Windows 7 Starter you can change the desktop background, its just harder to get to then Windows 7 Home Premium.
According to this article, the way to change the desktop background is to go to the start menu and type "Change desktop background".