We had a problem with a SharePoint implementation recently. All of a sudden, document icons were missing from document libraries, the New... button did not work, the option "Edit with Microsoft Word" was missing, and so on...

The reason for all of this? Incorrect permissions on docicon.xml on the web front-end server. That file contains definitions of file types, their icon and how these files should be opened. Make sure that the file inherits its permissions from the parent. If only Administrators and SYSTEM have rights, it will not work (obviously).