You are being restricted by the particular theme that you are using, I believe. The theme template, by default, places any added blocks above the logo within the header and below any content.
My advice is to choose a different template (perhaps Zen) or learn how to manipulate the templates of a theme to get the results you want.
This book is pretty solid for learning how to theme: http://www.amazon.com/Drupal-Themes-Create-powerful-styling/dp/1847195660/ref=pd_sim_b_2