Multiple Linked Objects with unique Materials / Group Materials override
(step 1 from gandalf3's answer)

Set the material datablock to Object, then right click on the drop down and select Copy to selected This is important, if you skip this step 2 will not work.


Select all the objects you want to have the same material, with the active object having the material to be copied to all the others selected. Press CtrlL, and select Materials. It will now link the materials to the Object and not the Data.