I'm trying to open some SharePoint files with the full office apps, but the applications always crash the instant after opening the files.

This doesn't happen with files created using the sharepoint web interface and then opened with the client and some random files we have uploaded.

Any idea what is going on?

EDIT: I tried to use this question to fix the problem, but to no avail Unable to open office files in Office client

EDIT 2: The files do open correctly using Office Web Apps

EDIT 3: Interesting discovery. The crashes occur whenever any of the client apps, try to access the SP server. For example, I opened a Word instance and tried to save the default file (the empty document you begin with) to the SP server using the 'Save & Send -> Save to SharePoint option' and after choosing the place I wanted to save in the SP hierarchy and clicking 'Save' Word crashed. Same thing happened with both PowerPoint and Excel.

EDIT 4: Trying to track down the problem, I used fiddler to see the network operations that are going on and I word receiving a bunch of 401 responses when trying to open the files. Not all responses are 401 though, some are successes. I therefore tried to enable anonymous access for the Site Collection, but still no solution.