#nav {
    background: #fafafa url(../img/nav-bg.png) repeat-x; // здесь и до следующего комментария - код, который уже существует
    border-bottom: 1px solid #fff;
    border-top: 1px solid #e3e1d9;
    height: 39px;
    position: relative;
    z-index: 999;
    width: 100px; // фиксированная ширина, как и у контейнера ниже
    margin: 0 auto; // выравниваем по центруpadding: 0 15px; // добавляем поля, поля плюс ширина - искомые 1030пкс
}
#search {
    float: right;
    margin: 7px 25px 0 0; // меняем внешний отступ, я так и не понял, почему он поехал, видимо из-за position:relative родителя
}