Must be started by upstart to make sure it runs before any networking daemons

Binary package hint: shorewall

shorewall (and shorewall6) should be started by an upstart script in lucid and later. If started from /etc/init.d, shorewall might come up too late. Somebody might have already connected to a service (and may continue communication via an ESTABLISHED rule).

On lucid I see at least mysql, vsftpd, and rsyslog starting before shorewall sets up its rules.

It probably would be best to use the same start-on events as ufw:
,---
| # Make sure we start before an interface receives traffic
| start on (starting network-interface
| or starting network-manager
| or starting networking)
`--