Question: In deploying to a new (Solaris 9) environment recently, one of the steps was to copy a set of files and directories to their new location and then to apply the group UID bit (using "chmod -R g+s") to all files in the directory tree giving a mode of -rwxr-s--- to everything. The result was that none of our shell scripts would execute unless they were individually opened and re-saved. I should add that we had earlier set g+s on the target parent folder prior to copying files; this had set the initial mode on all the new directories to drwxr-s--- but the files had a mode of -rwxr-x---

Having eventually discovered which step caused the problem, we were able to cut out that step and proceed.

I would like, however, to understand what the "s" bit means when applied to directories and files, in the hope that this will explain why we had the problem in the first place.

Answer: 
For files it means that the file is executed as the group that owns the file, not the group user that executes the file belongs to. It is usable when you want to allow user to do something which for which he does not have the privilege. For example, for one DBMS I use, it is common to allow everybody to backup databases. Although only the 'dbms' group has read/write access to database file, the backup program has g+s set to allow anyone to access the database through it, but not directly.

For directories, it means that newly created directories will be owned by the group that owns the directory, not the group user that created the file belongs to. A good example for this is web space of sourceforge.net project. Imagine 3 developers maintaining the project website. Now, if one of them creates a file, only he can write to it (by default). To work around this, all users on the same project are in the same group as well, and directory has rws privilege for that group, so whoever creates the file, it gets created as readable and writable to the group.
To expand on your specific problem a little, it has already been noted that sgid executables can cause problems by granting users permissions they don't normally have. While this is an issue for any executable, it creates a potentially-exploitable race condition in the case of scripts (specifically meaning "files which execute by means of an external interpreter identified by a #! at the beginning of the file") which can be used to execute any arbitrary code with the script's permissions.

Unix deriviatives have implemented a number of schemes over the years which are aimed at mitigating or eliminating this vulnerability, most of which have included some form of prohibiting the execution of suid or sgid scripts entirely or requiring you to jump through a few hoops to enable it (usually on a script-by-script basis). One such scheme would be the cause of your inability to run the scripts after turning on their sgid flag.