What other security based software do you have that might block new startup entries, e.g. Spybot S&D (TeaTimer), AdAware (AdWatch), SpySweeper, Spyware Doctor (StartUpGuard or OnGuard), PrevX, WinPatrol, ProcessGuard, etc. ?
They could be blocking the startup entry for the UI, see image.