Comment 3 for bug 630292

I've investigated a little further. gnome-terminal connects a callback to the "activate" signal on the Edit menu:

  action = gtk_action_group_get_action (action_group, "Edit");
  g_signal_connect (action, "activate",
                    G_CALLBACK (edit_menu_activate_callback), window);

When not using the application menu (UBUNTU_MENUPROXY= ), this callback is fired whenever the Edit menu is opened.

However, when using the application menu, this callback is fired once when the terminal window opens and not when the Edit menu is opened.

This callback checks the clipboard and activates paste, hence this would seem to be the cause of this problem.