Changing The Baclground Color Using Photoshop

I try to edit a gif format graphics file and face the following problem.

for the background, i am able to use magicwand to seperate image object from the background. However, i cannot get the color I want from color palatte toolbar.

This is because before I opean an image, there is unlimited color in the color palatte toolbar for me to select. However, after I open the image file, there is only limited color in the color palatte toolbar for me to selected. (They only display the color which is found in the image). How do i add new color in the palatte color toolbar?

thank you.