If 'hide menubar' is selected, gnome-terminal on startup will create the menubar and then hide it, which causes the terminal to change size (and just looks sort of strange). It should probably not create it in the first place... (this is with gnome-core-0.99.8.1-3)
fixed in gnome-core-1.0.somethingorother.