Why won’t desktops stay in order? I have created a number of desktops in which to keep Safari, Mail, iCal etc. These are all kept in full-screen mode and I have unchecked the setting to automatically rearrange spaces, yet whenever I restart my Mac the Spaces have changed order. Any ideas why?
You have a race condition and the outcome of it is non-deterministic.

They desktops get created in the order the programs are full-screened. So first desktop goes to the first application that tells the OS it wants to be full screen and so on. Apparently, when you resume your applications after a restart, they resume windowed and tell the OS that they should be full screen as they where before you shut down. The order in which they tell this to the OS is non-deterministic on every boot. They tell the OS, when they tell the OS, and in no particular order. So your full screen applications appear in random order every time you boot.

As of OS X 10.7.2, you can quickly re-order your desktops by bringing up Mission Control and then dragging the windows shown along the top of the screen in to the order you desire. Pre-10.7.2 you have to un-full screen all your applications and then re-full screen them in the order you want them to appear.