If you take a look at the standard it doesn't say you cant do this. It only says the header element cant be a decendant of an address or footer element. So go for it.
header - http://www.w3.org/TR/html-markup/header.html
nav - http://www.w3.org/TR/html-markup/nav.html
Generally speaking it would make sense for the nav element to be a child of the header element, or for the two to be separate.