SP2010: Unable to publish workbook to Excel Services

While trying to publish a workbook to SharePoint 2010 to use with Excel Services, I ran into some problems. Specifically, it appeared that Excel wasn't able to access my Document library.

To publish my workbook, I followed instructions you might find anywhere on the web, using the Office 2010 Backstage to save to SharePoint. However, none of my libraries showed up by default. Not a problem! I can just type the URL into the address bar, right? Apparently Excel says that it "can't open this location using this program".

Generally problems like this are permissions related. Well, I was logged into the machine as my farm administrator, who has full rights to the Documents library. I was also able to click on files from SharePoint and have them open Excel automatically.

I decided to take a new approach. I opened the demo Excel workbook that came with the Business Intelligence Center template. I then made a small update and saved it back to SharePoint. Now when I opened Backstage to save to SharePoint, the Documents library showed up in the Recent Locations section.

I was hoping by doing this, I could trick Excel into finding the location. So I then tried to save my new workbook by just clicking on that recent location. However, Excel was still not able to do it, and told me it was unable to open my site:

After looking around on the web, I found a forum post that seemed promising, as I'm using a Windows Server 2008 R2 machine. I opened Server Manager and installed the Desktop Experience, which required me to install the Ink and Handwriting Services as a prerequisite. I was then prompted to reboot upon completion. After rebooting, I attempted to save my workbook to SharePoint again and it worked.