You can set material overrides over Linked Objects! (Thanks IdeasMan)
Wiki:
http://wiki.blender.org/index.php/Extensions:2.6/Py/Scripts/3D_interaction/Oscurart_ToolsInstallation:
You must download the entire folder, and put in bin/2.6x/scripts/addons_contrib/
If addons_contrib folder not exist add it!
----------------------------------------------------------------------------
----------------------------------------------------------------------------