The Start Menu doesn't yet support directly changing user picture. It shows the same picture as the one set by Windows.
On Windows 8, you have to open "PC Settings -> Personalize" (the Modern Control Panel) to change the user account picture. You can open "PC Settings" from the Start Menu's search box without having to use the silly touchscreen gestures. Unfortunately, once you get there, browsing to the correct folder from the "File Picker" to set the user picture inside Metro is really terrible.
If you are using a Microsoft Account on Windows 8, you can set the picture in your online profile at
https://profile.live.com and it will change in the Start Menu as well.