El problema de siempre, no has aclarado el float y eso es lo que pasa, cuando flotas un elemento rompes el flow de pagina, asi que hay que devolverselo, mira usa este codigo:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/2000/REC-xhtml1-20000126/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="cs" lang="cs">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<style type="text/css">
/* Comienza id #menu */
.clear {
clear: both;
height: 0;
}
#contenido {
border:1px solid #66FF66;
background-color:#CCCCCC;
}
#leftcol {
width: 18%;
float: left;
}
#rightcol {
float:right;
width:81.3%;
}
</style>
<title></title>
</head>
<body>
<div id="contenido">
<div id="leftcol">
Esto es la parte izquierda<br />
dsadsadsa
</div>
<div id="rightcol">
Esto es la parte derecha
<br />
dadsadsa
</div>
<br class="clear" />
</div>
</body>
</html>