By default, when you duplicate objects, Blender does not duplicate the material datablock that those objects use -- it only creates links. If your objects are linked to the same material, instead of linking to different materials, then you'll get the behavior you're seeing.
There are two ways to change that behavior:
- go into the User Preferences panel and select "Material" under the "Duplicate with object" section, which is easier if you know that you'll need that sort of duplication beforehand
- make the materials single-user, by clicking on the number to the right of the material name. The number next to the material name is the number of links to that material.
I have uploaded an example of material linking here:
http://207.67.66.160:2242/~trythil/materials.blend
This is a block of text that can be added to posts you make. There is a 512 character limit.