I had this EXACT problem tonight and after about an hour of digging through Google links I found a solution that was not so much steam-based but permissions-based within the registry.
Open Regedit and find your HKEY_CLASSES_ROOT\steam key. Click it, and after it tells you that you don't have permissions to view it, right click the key "folder" and select Permissions. You will probably notice that the list of allowed users under Groups or User Names is blank. Click the Add button and add any user groups you want to have access to Steam (I added "Administrators", "SYSTEM", and my user name). Then select Administrators, and make sure that group has full read/write access to the key. Click OK. If the interface gives you guff about not having permission to save because you are not the owner, Click the Advanced button, select the Owner tab, and make sure Administrator and any other users you added are listed as owners (I omitted SYSTEM as owner, and it worked fine for me).
Once you have permissions to the key you will see the values are there, Now do the same for all the other keys.
One odd thing to note, after giving myself permissions for the Shell key, I couldn't see the Shell\Open or Shell\Open\Command keys. As I was creating a new key under Shell to make my own "Open" key, it suddenly appeared and I could edit permissions on that key. Same deal with Shell\Open\Command. A simple refresh might work, I didn't think to try that
After making all the permission changes, I closed regedit and launched Steam, and the steam:// protocol was fixed.
My free Portal demo is downloading as I type this :D