OK so you dont have DisableLocalMachineRun in the registry correct?
From what I can find those are the only 2 ways to disable the startup items.
As a test, create a new user account, login to that account and add something to the startup in the run key and see if it works for that user.
That would at least help me see if the problem is something with the user account.
Oh and as a test as well, turn off UAC in the control panel.
When I make my programs I found that I had to use the task scheduler to load startup items because I could run them with admin rights, when UAC is on you cant run a program from the run regkey with admin rights.
Shane