OK, after trying several things, I tried adding an LSB header:
### BEGIN INIT INFO
# Required-Start: $network $local_fs $named
# Default-Start: 3 4 5
# Default-Stop: 0 1 2 6
# Short-Description: Starts/stops the foo service
# Description: Starts/stops the foo service
### END INIT INFO
This worked! The script now runs after the network is initialized. I guess the systemd
implementation reads the LSB header.