Are you clicking OK/Apply/OK after you make the change?
I would like to keep my start-menu icons permanently small and this is what I do:
Right-click on Start button--->Properties--->Customize--->Show Small Icons in Start Menu (I check the box)
Trouble is each time I reboot the menu is back to large icons again
Perhaps theres a registry entry I can twiddle to make this permanent? Would really appreciate any help!