I think that web site navigation is one of those personal things that you either like or you hate.
When I design a web site, I like to create navigation that is user friendly first. After all, no matter how creative or cutesy it is, if a user cannot find things, the designer has failed with the navigation.
The article 25 examples of creative navigation on vandelaydesign.com shows 25 very creative uses in navigation.
My favorite of the 25 sites is Ben Hulse Design for the clean, simple, user friendly navigation. I love how he has integrated the simple design element of the arbitrary colors on the painted tile floor to the navigation links. Simple yet brilliant at the same time and it does not take away from the simple usability either.
Take a look at the article and shout at me your comments.