Hola, hice una prueba con ese código y aparentemente funciona bien (si esta es la imagen que debe repetirse 'http://www.costadoradavip.com/wp-content/uploads/fondoheader.png').
Te recomiendo que hagas la prueba en un archivo nuevo, si funciona quizas tengas otra cosa que te esté causando problemas.
<head>
<style type="text/css">
#header {
width:100%; height:120px; position:fixed; top:0; left:0; z-
index:100; padding:10px 0 0px 0; overflow:hidden; }
#header{
background:#1b1b1b url('http://www.costadoradavip.com/wp-
content/uploads/fondoheader.png') repeat-x;
}
</style>
</head>
<body>
<div id="header">
</div>
</body>
saludos