I just downloaded blender onto my Eee PC with Linux. I tried to create two different materials and assign them to two different objects, but whenever I change one of the materials, the other changes to the same thing and both objects are painted with the same color.
The objects are probably sharing the same material. Select one of your objects, and go to materials, and select ‘add new’. Now when you change it, it will only change on one object. Unless they are data linked, which is probably not the case.