When you change shuffle mode, do the icons in the title bar change to represent the selected shuffle mode? If not, then maybe there is a problem with storing configuration in gconf.