Yo pondría ese fondo en el body.
Pero bueno, también se puede hacer desde ahí. Primero, como es relativo al elemento padre, el elemento padre también tiene que ocupar el 100%, que, a su vez, también tiene que ocupar el 100% del elemento padre. Los padres son body y html. Así que estos tienen que tener una altura de 100%:
Ahora sólo hay que poner ese elemento también con una altura de 100%, pero como tienes la cabecera y el menú arriba, que miden 59 y 15 pixeles respectivamente, hay que restárselos a esa altura (ya que si no #contenido crearía un scroll de 59+15 pixeles). Para esto puedes usar calc() tal que:
Código CSS:
Ver originaldiv#contenido {
height: calc(100% - 59px - 15px);
}