I started looking at this a bit. The only upstream bug I can find that sounds similar is https://bugzilla.gnome.org/show_bug.cgi?id=600876 which talks about the same issue on Fedora 11, back at the end of 2009. But the maintainers couldn't reproduce.
** Bug watch added: GNOME Bug Tracker #600876 https://bugzilla.gnome.org/show_bug.cgi?id=600876 -- You received this bug notification because you are a member of Ubuntu Bugs, which is subscribed to Ubuntu. https://bugs.launchpad.net/bugs/630383 Title: Gnome-terminal paste keyboard shortcut does not work - menu not shown -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs
