I managed to solve the problem with some help from debian IRC channel.
The problem lied in the /etc/network/interfaces, where my eth0 interface was set up with the 'allow-hotplug' directive.
Still wondering why I ever did that... oO
In short, that allowed the interface to be declared 'mounted' while still unavailable. Services requiring the network to be up were then confused and reported heavy errors. nginx was one of those.
Reverting to the standard 'auto' solved the problem and the dependency is now met.