I used to get 'Not enough server storage is available to process this command' error on my server and found out the issue was server doesn't have enough continues free memory to handle the command. Rebooting server did fix the problem in my case. What's os and sp level on sandbox by the way?