Should I use <ul>s and <li>s inside my <nav>s?

the nav element and the list provide different semantical information:

• The nav element communicates that we're dealing with a major navigation block

• The list communicates that the links inside this navigation block form a list of items

At http://w3c.github.io/html/sections.html#the-nav-element you can see that a nav element could also contain prose.

So yes, having a list inside a nav element does add meaning.

At this point, I'd keep the <ul><li> elements, reason being that not all browsers support HTML5 tags yet.

For example, I ran into an issue using the <header> tag - Chrome and FF worked like a charm, but Opera borked.

Until all browsers support HTML completely, I'd stick them in, but rely on the old ones for backwards compatibility.

No, they are equivalent. Remember, HTML 5 is backwards compatible with HTML 4 lists, so you can feel free to use them in the same regard. The trade off is less code for the 2nd version.

If you are concerned about backwards compatibility with respect to browsers, make sure to include this shim to provide functionality of tags such as <nav> and <article>.