This doesn't seem quite the same as Bug 35785 which is for Windows 7. Applies to 3.5.0, 3.5.1rc2 and 3.5.1. The 'Recent Documents' sub-menu does not get populate as you save documents. This is the case for at least Writer and Calc. The sub-menu permanently reads 'No Documents'.
Created attachment 58500 [details] screen shot of empty menu Screen shot of empty menu on Fedora 14.
This most likely is a duplicate of bug 46074, see <https://bugs.freedesktop.org/show_bug.cgi?id=46074#c32> for the manual intervention that may be necessary to resolve it. *** This bug has been marked as a duplicate of bug 46074 ***