I got a weired issue with Linux clients while it worked fine with Windows machines. For some reason, the /etc/resolv.conf did not get updated. I found out a workaround thanks to this page. Of course, your server configuration file must contain (if 192.168.1.1 is your DNS server):

push "dhcp-option DNS 192.168.1.1"

First, you will need the resolvconf program. In debian :

$ apt-get install resolvconf

Then, you will need to add these lines into the configuration file of your Linux client (let’s say /etc/openvpn/client.conf) :

up /etc/openvpn/domain.up plugin /usr/lib/openvpn/openvpn-down-root.so /etc/openvpn/domain.down

The plugin provided by OpenVpn gives back root privilege (when initialized, OpenVPN needs root access but drops it soon).
Now let’s create the scripts :

/etc/openvpn/domain.up :

 #!/bin/sh
    # really naff script to add nameserver entry on up
    DEV=$1    
    set | sed -n "      s/^foreign_option_.* DNS \(.*\)'/nameserver \1/; T next; p;
    :next; s/^foreign_option_.* DOMAIN \(.*\)'/domain \1/; T; p;
      " | resolvconf -a $DEV
    resolvconf -u

/etc/openvpn/domain.down :

 #!/bin/sh
  # really naff script to delete nameserver entry on down
  DEV=$1
  resolvconf -d $DEV
  resolvconf -u

Now let’s give them the suitable rights :

$ chmod +x domain*

Finally, just restart openvpn and that should be fine !

UPDATE 2008/07/11 : The two scripts above are kind of obsolete, because, at least in Debian Etch, a similar script is included in the OpenVPN package.

There it is :

#!/bin/bash
# 
# Parses DHCP options from openvpn to update resolv.conf
# To use set as 'up' and 'down' script in your openvpn *.conf:
# up /etc/openvpn/update-resolv-conf
# down /etc/openvpn/update-resolv-conf
#
# Used snippets of resolvconf script by Thomas Hood <jdthood@yahoo.co.uk> 
# and Chris Hanson
# Licensed under the GNU GPL.  See /usr/share/common-licenses/GPL. 
#
# 05/2006 chlauber@bnc.ch
# 
# Example envs set from openvpn:
# foreign_option_1='dhcp-option DNS 193.43.27.132'
# foreign_option_2='dhcp-option DNS 193.43.27.133'
# foreign_option_3='dhcp-option DOMAIN be.bnc.ch'

[ -x /sbin/resolvconf ] || exit 0

case $script_type in

up)
	for optionname in ${!foreign_option_*} ; do
		option="${!optionname}"
		echo $option
		part1=$(echo "$option" | cut -d " " -f 1)
		if [ "$part1" == "dhcp-option" ] ; then
			part2=$(echo "$option" | cut -d " " -f 2)
			part3=$(echo "$option" | cut -d " " -f 3)
			if [ "$part2" == "DNS" ] ; then
				IF_DNS_NAMESERVERS="$IF_DNS_NAMESERVERS $part3"
			fi
			if [ "$part2" == "DOMAIN" ] ; then
				IF_DNS_SEARCH="$part3"
			fi
		fi
	done
	R=""
	if [ "$IF_DNS_SEARCH" ] ; then
        	R="${R}search $IF_DNS_SEARCH"
	fi
	for NS in $IF_DNS_NAMESERVERS ; do
        	R="${R}nameserver $NS"
	done
	echo -n "$R" | /sbin/resolvconf -a "${dev}.inet"
	;;
down)
	/sbin/resolvconf -d "${dev}.inet"
	;;
esac