Because of how <div> sections and stylesheets operate — the sidemargin had to be setup as a background image.

If you want to modify it (without creating a new custom-style), you can simply replace the "cont-bg.gif" file in the "imgs" folder of your Market Theme files.  Just open that image, and then flood fill the color on the left side.

Save and upload, and that'll do it.

Before you change the color of the image, increase the colors to 16 million (or whatever the highest is).

As you describe it, it sounds like it's exactly like what I said.

In photoshop, you'll need to load the image — then increase the color depth.  Then you can fill it with any color.

Currently, the image is probably only set to 3 colors.