It seems to have stopped working for me on 16.04, updated to latest versions.
I can open and save a file with a name but then the gedit menu open recent doesn't show it or any other ones I have opened or edited. Just has Reopen Closed Tab in gray.
Interestingly... the 'open' button does present my recent files, something I haven't seen before today
Running $/usr/bin/gedit
works does bring up gedit
(still with the issue), although this way I do get the following warning
(gedit:17233): Gtk-WARNING **:
Theme parsing error: gtk.css:1:25: Missing name of pseudo-class
This appears to be a confirmed issue that manifests with GEdit, Gnome and Ubuntu combination. Here is a link to the bug - https://bugs.launchpad.net/ubuntu/+source/gedit/+bug/1570227
I do realize that this is not an answer but I can't really add a comment to the question due to lack on enough points, which is why this "answer".
I'm using Mint 18.1, but it's based on Ubuntu 16.04.
When I found this question, I wasn't even getting the recent files in the Open/ menu. It appears that the gedit developers are planning to move to that way of displaying recent files. However, I wasn't getting recent files in GIMP either, but I found some information that explains why.
Solution
Look under Preferences → System Settings → Privacy for the option to Remember recently accessed files. After enabling that, I get my document histories in the Ubuntu based applications again.
This appears to be a system-wide issue, not directly caused by gnome packages. I have actually first noticed it with mousepad (part of xfce wm) after Linux Mint 18.1 system upgrade. Gedit was also affected by same update.
Only mentioning this since the gedit bug mentioned above concerns a newer ubuntu version.
Regardless of version you should first check gedit's hidden preferences with dconf (or dconf-editor) here: org.gnome.gedit.preferences.ui.max-recents
example reading max-recents value using dconf:
you can also change the same value, ex.: