Ouch, yikes.
I looked through your dropdown list of backgrounds, and the only ones that I think are workable at all are the dark rock ones... the rest are insta-headaches. Also, any time you're going to use a solid color box (in your case, the black ones) on an image background, you really have to border them, otherwise they just look wrong.
As for your links, it looks to me like you've just used the default font settings and colors there, which would explain Stephanie's comments. Try changing the link and vlink parameters in your body tag to a different color - experiment until you find a color that works, if you're not sure - and use a font tag for your links so they're not just 2pt. Times New Roman. That will help spruce your navbar up a lot.
As for the header logo, I concur with Stephanie - either left align it, or center it - the random placement throws the whole site layout off.
Good luck!