Together with another thread I figured it out. Where Juggledad was working on a table problem in the header.
If you use this it works and your header will be centered.
<a href="/"><img class="aligncenter" src="/wp-content/themes/atahualpa342/images/my-logo.gif" alt="My site title" /></a><br />
Thank you all for pointing me into the right direction. With all the ideas from Flynn and Juggledad I was able to figure it out. I couldn't be happier!
You can see it works. Please surf to
http://stonefencedrive.com/test/