The following worked for me!  
Tried all of the previous answers, but none worked.  
Then I came across a fix described [here on Apple Forums][1]:  

First round (tried, but did not work for me):

Open terminal, and type:

    sudo find ~ $TMPDIR.. -exec chflags -h nosappnd,noschg,nosunlnk,nouappnd,nouchg,nouunlnk {} + -exec chown -h $UID {} + -exec chmod +rw {} + -exec chmod -h -N {} + -type d -exec chmod -h +x {} + 2>&-

Second round (this one did work for me):

 - Start up in Recovery mode.
 - In recovery mode, launch terminal (from utilities menu)
 - Type "resetpassword" and hit enter (no worries)
 - Select your startup volume
 - Select relevant user
 - At the bottom, under Reset Home Directory Permissions and ACLs, click Reset
 - I repeated the last to steps for all users + root
 - Restart your computer

The description on Apple Forums is really clear, so if in doubt, go there. Hopefully it will help others too.

FYI: All my recent items were gone in all apps, in Apple menu the whole menu item was even gone, and changing in System Preferences from none to whatever kept reverting back to none.  
I am on a MacBook Air (early 2014), running El Capitan 10.11.3


  [1]: https://discussions.apple.com/message/29365156#29365156