I also had this problem and after many hours of testing have found a solution......well it worked for me anyway.
Group Policies!!!!!
I put a test user in an OU that had only default domain policies linked to it and tested the save & browse buttons in Excel & Powerpoint 2013, it worked.
One by one i added in additional group policies, restarted, tested, until i found a GP that broke the buttons.
In my case it was a 'Known Folder' i had disabled, the Desktop Folder {B4BFCC3A-DB2C-424C-B029-7FE99A87C641}. I have a heap of 'Known Folders' disabled as we are a school, I don't want the students saving locally as nearly everything is redirected.
I never had any issues with Office 2010 with these disabled folders but for some reason Office 2013 doesnt like them.
User Configuration / Administrative Templates / Windows Components / File Explorer / Disable Known Folders.
I would be interested to see if this is the case for other people experiencing this problem.