Since nginx-gridfs connects to mongodb, the db server should already be running and ready. This was causing a problem.
First I removed the /etc/init.d/nginx script using 'update-rc.d remove nginx'
Then I created an 'upstart' script in /etc/init/nginx.conf :

# nginx



description "nginx http daemon"



#start on mongodb  

start on (local-filesystems

    and net-device-up IFACE=lo

    and started mongodb) 

stop on stopped mongodb



env DAEMON=/usr/local/nginx/sbin/nginx 

env PID=/usr/local/nginx/logs/nginx.pid



expect fork 

respawn 

respawn limit 10 5



pre-start script

        $DAEMON -t

        if [ $? -ne 0 ]

                then exit $?

        fi

        # Add a sleep of 10 sec. to allow mongodb to finish starting up

        sleep 10 

end script



exec $DAEMON

This fixed the problem for me.