Yeah this problem is annoying.
Another solution would be to have the container div the colour you want your nav to be, then make the contents to be another colour:
<style>
#page { background-color:blue; width: 996px; etc }
#contents { background-color:red; etc }
</style>
<div id="page">
<div id="sidebar">
</div>
<div id="contents">
</div>
</div>
ends up looking like:
_____________________
| | |
| | |
| | |
| | |
|___| |
|___|_________________|
with the divs, but the colour of the background "page" will be on the left, and the background of the content will be on the right
I hope that helps. This suffers from when the right is smaller than the left :(
edit:
you can also use bg images if you so wish in this format. This is something that is very awkward to do in html/css and you just need to play until you get a solution which fits you. This took me days to research for my site :(