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, everything started to work correctly. Who knows the real reason this happened, but here is the solution!