SP 2010

Library configured to open documents in the client application.

User 1 has full control on library and document.

User 1 clicks on Excel document.

User 1 is prompted for folder into which document should be saved.

User 2 also has full control on library and document

User 2 clicks on Excel document.

User 2 is presented the document within Excel.

The only time I have seen behavior like this before was when a site had custom permissions (created under SP 2007) and those permissions was not at the time granting the user the right to open a document in the client.

This time, the user has out of the box Full Control permissions (yes, I checked the site settings for full control to ensure the attribute was assigned).

Admins have already reinstalled SharePoint related Office components. They also ran an office repair and had the user reboot their desktop.

Any other ideas on what might be going on?

Try User 2 on a different machine. I'm pretty sure this is the result of a setting that gets saved (possibly in the registry) when a user first hits SharePoint from a computer asking them if they want to cache the files locally.

To confirm that it's not user rights or connectivity you can get the user to copy the link to the item then open Excel and try to open the document from the application. If it opens from Excel you've demonstrated that the application and the user have the rights and settings needed to open the document directly.