I struggled with this for a good hour. I'm using 10.6.2 in 64-bit mode (in case that matters). I tried everything suggested: editing the plist file in vi, using the plist editor, using the defaults command, etc. My method was always:
1. turn off Internet Sharing
2. Do my editing
3. turn on Internet Sharing

My results were always the same. It always used 192.168.2.0 for the network. It always overwrote my modified plist file with one that did not include my SharingNetworkNumberStart node. I tried putting that node in various places in the plist. I didn't get any success at all.

Finally, in a fit of frustration, I edited the /usr/libexec/InternetSharing binary. Amazingly, this works:
1. sudo cp /usr/libexec/InternetSharing /usr/libexec/InternetSharing-orig
2. sudo vim /usr/libexec/InternetSharing
3. Search for the string 192 in the binary. You'll find it in 3 places IIRC.
4. In order to keep everything exactly sized correctly, I just changed 192.168.2.0 to 192.168.9.0.
5. Start Internet Sharing in the System Preferences.

It worked. I think it stinks, and if there's an update to OSX, I'll probably have to go do this edit again.

You were almost there - just add steps 1.5 and 2.5 to get the settings to stick.

1. turn off Internet Sharing
1.5. quit System Preferences
2. do my editing
2.5 relaunch System Preferences
3. turn on Internet Sharing

It seems that System Preferences is cacheing the contents of com.apple.nat.

Now, anyone have any idea how to change the net_ange that the resulting DHCP server serves up from the default of x.x.x.2 - x.x.x.254?