not:first-child selector

One of the versions you posted actually works for all modern browsers (where CSS selectors level 3 are supported):

div ul:not(:first-child) {
    background-color: #900;
}

If you need to support legacy browsers, or if you are hindered by the :not selector's limitation (it only accepts a simple selector as an argument) then you can use another technique:

Define a rule that has greater scope than what you intend and then "revoke" it conditionally, limiting its scope to what you do intend:

div ul {
    background-color: #900;  /* applies to every ul */
}

div ul:first-child {
    background-color: transparent; /* limits the scope of the previous rule */
}

When limiting the scope use the default value for each CSS attribute that you are setting.

This CSS2 solution ("any ul after another ul") works, too, and is supported by more browsers.

div ul + ul {
  background-color: #900;
}

Unlike :not and :nth-sibling, the adjacent sibling selector is supported by IE7+.

If you have JavaScript changes these properties after the page loads, you should look at some known bugs in the IE7 and IE8 implementations of this. See this link.

For any static web page, this should work perfectly.

Since :not is not accepted by IE6-8, I would suggest you this:

div ul:nth-child(n+2) {
    background-color: #900;
}

So you pick every ul in its parent element except the first one.

Refer to Chris Coyer's "Useful :nth-child Recipes" article for more nth-child examples.