How can I change the colors of GNOME Terminal each time it starts?

I haven't seen the script you mention. But I think it is possible to create such a script.

Gnome Terminal picks up the background colour from the profile in use, so any change will impact the background colour of all terminals using the same profile.

That said, the configuration key is stored in /apps/gnome-terminal/profiles/Default/background_color, where Default is the currently used profile.

It can be set thus:

gconftool-2 --set "/apps/gnome-terminal/profiles/Default/background_color" --type string "#E376DDDDFFFF"

So, I'm guessing that one can write a script to clone the Default profile on the fly, change it's background_color, invoke gnome-terminal with this profile, and delete the profile before exiting. You'll also need a database of good foreground/background color combinations for this script to use.

Update: Here is a script to do what is discussed above. It does not generate a random background color, that you'll have to generate using some list.

#!/bin/bash 

PROFILE_NAME=${RANDOM}_p_${RANDOM}
TMP_DIR=/tmp
DEFAULT_PROFILE=Default
PROFILE_EXPORT_FILE=${TMP_DIR}/${PROFILE_NAME}.xml

#replace with program to generate a random background color
BACKGROUND_COLOR="#0000AA000"

# dump the "Default" profile, replace with new random profile name
gconftool-2 --dump /apps/gnome-terminal/profiles/${DEFAULT_PROFILE} > ${PROFILE_EXPORT_FILE}
sed -i "s/${DEFAULT_PROFILE}/${PROFILE_NAME}/g" ${PROFILE_EXPORT_FILE}

# load the new random profile, change the background color
gconftool-2 --load ${PROFILE_EXPORT_FILE}
gconftool-2 --set "/apps/gnome-terminal/profiles/${PROFILE_NAME}/background_color" --type string "${BACKGROUND_COLOR}"

# add the new random profile to list of profiles
PROFILE_LIST=`gconftool-2 --get /apps/gnome-terminal/global/profile_list`
NEW_PROFILE_LIST=`echo $PROFILE_LIST | sed "s/]/,${PROFILE_NAME}]/g"`
gconftool-2 --set  /apps/gnome-terminal/global/profile_list --type list --list-type string "$NEW_PROFILE_LIST"
# start gnome-terminal with new random profile, such that the script blocks till terminal is closed.
gnome-terminal --window-with-profile=${PROFILE_NAME} --disable-factory

# cleanup: remove the new random profile, and remove it from list of profiles
gconftool-2 --recursive-unset /apps/gnome-terminal/profiles/${PROFILE_NAME}
PROFILE_LIST=`gconftool-2 --all-dirs /apps/gnome-terminal/profiles | sed "s/ \/apps\/gnome-terminal\/profiles\///" | sed -n -e 'H;${x;s/\n/,/g;s/^,//;p;}'`
gconftool-2 --set  /apps/gnome-terminal/global/profile_list --type list --list-type string '['"${PROFILE_LIST}"']'