I found the solution for this problem. I figured I would post it here just incase google leads another poor sharepoint user, with this problem, to this topic.
There is an Internet Explorer add-on that somehow got disabled on the clients machine.
SharepointOpenXMLDocuments.
I have no idea how it got disabled, but once I reenabled it, ...