The usefulness of <nav> is questionable, but HTML5 introduces plenty of new tags and attributes that you can and should be using today.
It's perfectly acceptable to use HTML5, regardless of what some people here might say. Older browsers don't support the new tags, but the web shouldn't be about dumbing down our code to make sure obsolete pieces of software can read it. The web should be about moving forward.
You're right in your assumption that HTML5 elements can help with SEO. It might not make a difference now, but down the road, Google will be taking advantage of the new tags. They might use <nav> to show a list of links in the search result. I can tell you right now they'll be using <time> to organize results based on date. And then the people who insisted on sticking with HTML4/XHTML because "HTML5 is nothing but sloppy code and tags for nothing" will be wishing they'd taken advantage of this stuff earlier on.
The new tags AREN'T for nothing...they have a real purpose, and anyone who doesn't see that purpose can't seriously say that they understand the value of semantics in HTML.
Sure, there's a certain point when a <div> or a <span> or a <p> will do just fine, but things like <header>, <article>, <section>, <aside>, <footer>...they help define the different parts of a page. And don't let anyone tell you that these elements are presentational. They're not. <header>, for example, isn't simply "some **** at the top of my page". It's a space for introductory content. You could technically use CSS to put your header at the bottom of the page, though I'm not sure why you would.
I say use HTML5, use CSS3, and use every excuse to forget about versions of IE that people shouldn't be using anymore in the first place. If even Microsoft wants you to stop supporting IE6 and IE7, it's time to stop supporting them.
Some people say it's the designer's responsibility to make sure anyone can see their design in its full glory...but at the same time, it's the viewer's responsibility to understand how to use a computer properly and upgrade their browser.
Just use an HTML5 shiv, make sure all your content is accessible to everyone (even if it might not look pretty), and you're good. Welcome to the future.