I've done this twice this week.
Create new region in .info file, run cron, go to Blocks page to assign something to it and POING! It hops to the Left Sidebar. Look at code in .info and page.tpl.php, run cron again, try again. Same problem.
Upon closer inspection - when I pasted over my fancy new region name into my .info file - I brought over the preceding $ so I had:
regions[$myregion] = Stupid Region for Jerks
This doesn't break badly enough to give you any sort of error, and your region will show up on the Blocks page giving the illusion that everything is okay, but when you attempt to assign anything there it hop to the next available region.
Removing the stray $ fixes the problem.
regions[myregion] = Stupid Region for Jerks
But you'll have to run cron again before it will work.