I lost hours figuring this out. Just because the Devs at Magento aren't capable of making an understandable configuration, or yet even documenting their code in a way a human being would be able to read it.
Let's have a look at the config.xml first
<routers>
<adminhtml>
<args>
<modules>
<admin_adminhello after="Mage_Adminhtml">Pulsestorm_Adminhello_Adminhtml</admin_adminhello>
</modules>
</args>
</adminhtml>
The whole meaning of the Tags has changed. The Tag under "modules" is just a random name. you just need to make sure its unique to ensure it is not overwritten when the XML is compiled. It has influence on the URL.
<admin_adminhello after= ..... >
Magento now expects you to move your backend controller classes into a new subfolder called "adminhtml" This is why in the config.xml you have to change the class name prefixsuffix by adding _Adminhtml.
... >Pulsestorm_Adminhello_Adminhtml</admin_adminhello> ....
In your case the folder would be located at
app/code/local/Pulsestorm/Adminhello/controllers/Adminhtml
Now the real Problem. Using the other (better) system you had your own namespace defined by using the "FrontName" Tag. You don't have this luxury any more, so you need to make sure your controller has a unique name. Otherwise it would conflict with other Extensions. So controllers named something like "AdminController.php" are no longer good, you have to make it something project specific, like in your case "AdminhelloController.php"
Your URL will then chagne to
http://localhost/index.php/admin/adminhellobackend/index/key/83f08ec4bddff37e47412e16acc8d3f6/
Don't forget to adjust the controller classname after renaming or moving the file
/app/code/local/Pulsestorm/Adminhello/controllers/Adminhtml/AdminhellobackendController.php
In this case the name would be Pulsestorm_Adminhello_Adminhtml_AdminhellobackendController
Of course you must also adjust any URLs used in menu items and forms that you use in the backend
Also make sure you switch on Developer Mode in the index.php file. I noticed that if the controller has some bug in it, you also get a 404. With Develeport mode you get a Stacktrace error.
What I would also do, is just write a log once the controller is called, just so that you see if the controller method was accessed at all.
/app/code/local/Pulsestorm/Adminhello/controllers/Adminhtml/AdminhellobackendController.php
class Pulsestorm_Adminhello_Adminhtml_AdminhellobackendController extends Mage_Adminhtml_Controller_Action
{
public function indexAction()
{
Mage::log('Controller was accessed', null, 'controller.log', true);
$this->loadLayout();
$this->_title($this->__("My Test Page Title"));
$this->renderLayout();
}
}