The connection is based on openvpn, and it's the same on many other nodes, but openvpn wasn't starting properly (no sign of the tun interface).
Googling the problem brought me to this reported debian bug, where apparently the problem was associated to an older version of the linux kernel. But I had the latest installed:
ii linux-image-3.2.0-4-amd64 3.2.63-2+deb7u1 amd64 Linux 3.2 for 64-bit PCs
The reason why this problem was present is that the version actually loaded was different!
[...] it seems that grub settings are ignored
on digital ocean, and that you instead have to specify which kernel is
booted from the Digital Ocean control panel, loaded from outside the
Debian 7.0 x64 vmlinuz-3.2.0-4-amd64 (3.2.54-2)