Why can't I center with margin: 0 auto?

You need to define the width of the element you are centering, not the parent element.

#header ul {
    margin: 0 auto;
    width: 90%;
}

Edit: Ok, I've seen the testpage now, and here is how I think you want it:

#header ul {
    list-style:none;
    margin:0 auto;
    width:90%;
}

/* Remove the float: left; property, it interferes with display: inline and 
 * causes problems. (float: left; makes the element implicitly a block-level
 * element. It is still good to use display: inline on it to overcome a bug
 * in IE6 and below that doubles horizontal margins for floated elements)
 * The styles below is the full style for the list-items. 
 */
#header ul li {
    color:#CCCCCC;
    display:inline;
    font-size:20px;
    padding-right:20px;
}

An inline-block covers the whole line (from left to right), so a margin left and/or right won't work here. What you need is a block, a block has borders on the left and the right so can be influenced by margins.

This is how it works for me:

#content {
display: block;
margin: 0 auto;
}

Why not?

#header {
    text-align: center;
}

#header ul {
    display: inline;
}