The ultimate solution:
Go to:
http://empty.23inch.de/pmwiki.php/Main/EditShortcuts
Download the tgz and install (Put the editshortcut.gedit-plugin file and the whole editshortcut directory into ~/gnome2/gedit/plugins. Restart gedit)
Edit>Preferences>Plugins: Edit Shortcuts (tick)
then
Tools>Edit Shortcuts:
GeditWindowAction->EditRedo: change to Ctrl+Y