Correct solutions were submitted by Ron Welch, Lou Cairoli, Cee Ann Franklin, Farid Lian and Paul Lee.
The smallest possible surface area is 700 square feet.
Clearly the dimensions of the box must be integers. Since the volume of the box must be 1000 cubic feet, these integers must be factors of 1000. Now it is straightforward to check the possible dimensions and find the ones that give the smallest surface area. It would seem that 10'x10'x10' would be optimal, but as we will see, this arrangement is impossible. The next-smallest surface area comes from 5'x10'x20', which can be achieved.
Why can't the packages fit into a 10'x10'x10' box? Here's one explanation: Divide the box into 1'x1'x1' cubes and label these according to their x, y and z coordinates, each of which runs from 1 to 10. "Color" each cube with the (x+y+z)th power of i (the square root of -1). Notice that each package includes cubes whose "colors" add to zero. Since the sum of all the "colors" in a 10x10x10 box is nonzero, filling such a box with packages is impossible.
Why does 5'x10'x20' work? Five 1'x1'x4' packages can be laid end-to-end to make a 1'x1'x20' unit, fifty of which can easily be arranged to fill a 5'x10'x20' box.