Comment 3 for bug 1482069

Confirmed, both the problem and the workaround, and it's present upstream too. The issue is described here:
http://www.freedesktop.org/wiki/Software/systemd/NetworkTarget/
Requiring only network.target means requiring NetworkManager to start, but not requiring DNS to be up; since miredo is started before DNS is up, and it can't cope with it, the result is failure.

The possible solutions/workarounds are: 1) As per above, require network-online.target (one can use /etc/systemd/system/miredo.service.d/network-online.conf or similar override instead of editing the whole file); 2) Enable NetworkManager-wait-online (not recommended as it slows down boot); 3) Fix Miredo to wait for DNS to be up by itself.