Why would a shutdown script NOT run?

You want the script to run on shutdown. Replace start with stop as follows:

sudo update-rc.d push-apache-logs-to-s3.sh stop 0 0 .

Note that it will get a K prepended, instead of an S

What's the expected behavior when you set the script to be run at S00? I have no scripts with S00 on my system, could it be that a minimum of 1 is required? You also did not explicitly set start/stop, perhaps that's causing problems. Just in case, try

sudo update-rc.d push-apache-logs-to-s3.sh start 01 2 3 4 5 . stop 01 0 1 6 .  

If that still doesn't work, please update your question to who your script (or at least its headers), there might be something wrong there.

EDIT

Having seen the script you posted in your other question, I see two possible problems. First, you have a space in your shebang line !# /bin/sh instead of #!/bin/sh.

More importantly, why are you using sh instead of bash? sh does not support source, let alone . as an alias for source. Change your script to run with bash instead, that should fix it. In fact I don't understand why it works when you run it manually, the . should throw an error:

$ sh
$ source foo
sh: 1: source: not found
$ bash
$ source foo
bash: foo: No such file or directory

Scratch that, I was wrong, as @gnp pointed out, dash does actually support ..