Perhaps you have a directive in your client config file that specifically demands that the tun0 device is to be used, expecting that you create it. You might instead get rid of that so it tries to create an interface by itself. You might want to post your client config (but with private key and username/password redacted of course) so people can actually have some clue about where it's going wrong.
Alternatively you can look into using network manager's OpenVPN plugin, and configuring the connection in there, and marking it as 'connect at startup' in network manager configuration.
