Check which locale you are using (mine is en_US, don't worry about the .UTF ending):
locale
Next, backup and edit the applicable locale file (use the result of the previous command if not en_US).
sudo cp /usr/share/i18n/locales/en_US /usr/share/i18n/locales/en_US.bak
sudo nano -w /usr/share/i18n/locales/en_US
Locate the following line and change the value. The value for Monday in en_US was 2. Select the appropriate number if you desire another day to be the start day.
first_weekday 2
Save the file and then:
Update the locales:
sudo locale-gen
Refresh the desktop:
killall gnome-panel
The first day should now be Monday