Centering a nav bar vertically

Here's a fork of your original fiddle. You need to be setting inline-block on your logo and the nav element itself:

header img, header nav {
    display: inline-block;
    vertical-align: middle;
}

Rather than trying to float things.