Padding är inte rätt att använda http://www.w3.org/TR/REC-CSS2/box.html för ie gäller denna http://en.wikipedia.org/wiki/Internet_Explorer_box_model_bug men med relative postion och left: x antal pixlar så kan du flytta den http://www.w3.org/TR/REC-CSS2/visuren.html ( 9.3 Positioning schemes ), men det är bättre att göra rätt från brörjan, det skulle vara lättare och du gav ut hela koden.. Kanske lägga upp den såhär någonting:
|-----------------
| DIV1 |
|-----------------
| DIV2 | D |
| | I |
| | V |
| | 3 |
------------------
Allt igger i en div som du har centrerat, div1 är bara en div med din logo som background, div2 är en div med float left och div3 är en div med float right. Det ska nog funka.
Vi får väll se om du kan klaga på det inlägget Malesca
edit: Det var vist så du hade gjort.. Bra att läsa innan, men testa med att sätta padding på din .container class, ser ut som att skugga ingår i den bakgrundsbild och därför finns även diven där och du menu diven hamnar utanför. margin-right: 15px; på .menu är nog det bästa föresen.