I installed a new theme on the site today and wasn’t satisfied with the regions offered for placing blocks. Luckily, I’m a brilliant hacker of code and knew how to add more. And I promise to you, in less than 5 minutes, you’ll know how to add new regions to a Drupal 6 theme too!
In each theme, you’ll have a .info file and a page.tpl.php file. You have others, but these are the important ones for adding regions. Assuming you have a theme named Awesome, your files would be Awesome.info and page.tpl.php.
Awesome.info is pretty straight-forward to edit.