Bueno pues ya probe lo que me dijeron y pues primero probe lo que dijo mikel, le quite el float:left al segundo cuadro(cajadetexto) y aun asi se caia, que aunque le quite el float left se mantuvo junto al otro div no dejo de caerse.
Luego probe lo de zega, suma el padding, los bordes y el ancho de las dos cajas y las meti dentro de otra caja, con ancho fijo y si funciono. Ahora ya no se caen. Gracias a los dos. Voy a poner el codigo por si a alguien le sirve:
<div id="contenedor" style="width: 702px; height: 400px; margin-left: 20%">
<div id="bienvenidos" style="height:400px; width:100px; float: left"><img src="Bienvenido.gif" width="100" height="400"/></div>
<div id="cajadetexto" style="height:380px; width: 580px; background-color: #FF2222; border-left: 1px dashed #EC0000; border-right: 1px dashed #EC0000; overflow: auto; padding: 10px;">
-SOLUCIONADO-
Lo que si tengo duda es que voy a hacer cuando quiera meter en un futuro 2 cajas como meti estas, pero en lugar de ser con ancho en pixeles una sea con ancho en pxeles y la otra en porcentaje.