Apple will of course take its sweet time in fixing this issue. In the meantime, here is a workaround. I tried to force Dock.app to restart using the command:
killall -HUP Dock
This caused the wallpaper to be properly updated on my primary desktop. Note that I use ML's "Spaces" feature and I have four virtual desktops. Virtual desktop 2, 3 and 4 display the proper updated wallpaper even upon startup. The problem lies only with the primary desktop.
To make this process easy, I have created an application called "Killall Dock.app". Drop this in your Applications folder and include this item in your Login Items (from System Preferences > Users & Accounts).
Download "Killall Dock.app"
Wrapper application "Killall Dock.app" created using the awesome Platypus.app :)
