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.