Comment 5 for bug 516016

Problem still exists in 10.04 (probably also 10.10).
Another workaround: Add a sleep time at the autostart section of /etc/init.d/openvpn before the "start_vpn" command.
if ! ip addr show dev eth0 | grep -q 'inet' ; then
  sleep 10
fi

Of course change eth0 to whatever device OpenVPN is listening on.