You need to define positioning for #primaryNav. Z-index only affects positioned elements.
I just added this in firebug and it fixed:
#primaryNav {
position: relative;
}
I would avoid using a negative z-index. Simply change z-index of #page to 0.